Restoran

Στην Κροατία υπάρχουν ~N~ πόλεις που συνδέονται με ~E~ διπλούς δρόμους. Δύο μεγάλες αλυσίδες τροφίμων κατέληξαν πρόσφατα σε συμφωνία για την κατανομή της αγοράς. Στη μέση κάθε δρόμου, ακριβώς σε μία αλυσίδα θα δοθούν δικαιώματα για την κατασκευή ενός εστιατορίου.
Για να διασφαλιστεί ότι η αγορά μοιράζεται δίκαια, κάθε πόλη πρέπει να έχει τουλάχιστον ένα εστιατόριο από κάθε αλυσίδα στους δρόμους που συνδέονται με αυτήν την πόλη. Ωστόσο, υπάρχουν πόλεις με μόνο έναν δρόμο ή καθόλου δρόμους, και για αυτές είναι αδύνατο να έχουν και τις δύο αλυσίδες. Τέτοιες πόλεις είναι καταδικασμένες να επισκεφτούν μια αλυσίδα ή να ταξιδέψουν λίγο παραπέρα.
Γράψτε ένα πρόγραμμα που θα καθορίζει για κάθε δρόμο την αλυσίδα που θα πρέπει να κατασκευαστεί εκεί ώστε να ικανοποιούνται αυτές οι απαιτήσεις.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N~ και ~E\;(1 \le N, E \le 100\,000)~, τον αριθμό των πόλεων και των δρόμων.
Οι επόμενες ~E~ γραμμές περιέχουν δύο ακέραιους η καθεμία. Κάθε γραμμή περιγράφει έναν δρόμο.
Οι ακέραιοι ~A_i~ και ~B_i\;(1 \le A_i, B_i \le N,\;A_i \ne B_i)~ δηλώνουν έναν δρόμο που συνδέει τις πόλεις ~A_i~ και ~B_i~.
Δεν θα υπάρχουν ποτέ δύο ή περισσότεροι δρόμοι που να συνδέουν τις ίδιες πόλεις.

Έξοδος

Εάν δεν υπάρχει τρόπος δίκαιης αντιστοίχισης των δρόμων, η πρώτη και μοναδική γραμμή εισόδου πρέπει να περιέχει το "0".
Διαφορετικά, τυπώνετε ακριβώς ~E~ γραμμές, μία για κάθε δρόμο, με την ίδια σειρά που δόθηκαν στην είσοδο. Η ~i~-οστή γραμμή πρέπει να περιέχει "1" εάν η πρώτη αλυσίδα έχει το δικαίωμα να χτίσει σε αυτόν τον δρόμο ή "2" εάν η δεύτερη το κάνει.

Σημείωση: εάν η λύση δεν είναι μοναδική, μπορείτε να τυπώσετε οποιαδήποτε είναι έγκυρη.

Βαθμολογία

Αυτή η εργασία έχει δοκιμαστικές περιπτώσεις ομαδοποιημένες σε δοκιμαστικές εκτελέσεις. Κάθε δοκιμαστική εκτέλεση (test run) αποτελείται από μία ή περισσότερες περιπτώσεις δοκιμής. Για να συγκεντρώσετε πόντους για τη δοκιμαστική εκτέλεση, όλες οι περιπτώσεις δοκιμών κατά την εκτέλεση πρέπει να επιλυθούν σωστά.
Δεν χρειάζεται να ανησυχείτε για τις δοκιμαστικές εκτελέσεις κατά την είσοδο και την έξοδο. Το σύστημα το κάνει αυτό για εσάς. Ακολουθήστε κατά γράμμα τη μορφή που περιγράφεται στο INPUT/OUTPUT!
Οι δοκιμαστικές εκτελέσεις αξίας ~60~% έχουν ~N \le 1000,\;E \le 5000~.

Παραδείγματα

input

5 6
1 2
2 3
3 1
3 4
1 4
4 5

output

1
2
1
2
2
1

input

7 7
1 2
2 3
3 1
4 5
5 6
6 7
7 4

output

0

input

77777 4
1 2
1 3
1 4
1 5

output

1
2
2
2