Molekule

Επιστήμονες σε ένα χημικό εργαστήριο στην Κροατία έχουν μελετήσει τους χημικούς δεσμούς μεταξύ διαφορετικών μορίων. Έχουν ιδιαίτερο ενδιαφέρον για μια ομάδα μορίων της χημικής ένωσης υδρογόνο ελασματοποιημένο.
Η ένωση αποτελείται από ~N~ μόρια συνδεδεμένα μεταξύ τους με ~N-1~ ομοιοπολικούς δεσμούς και όλα τα μόρια συνδέονται μεταξύ τους άμεσα ή έμμεσα με δεσμούς σε μια ενιαία δομή.

Οι επιστήμονες θέλουν να τροποποιήσουν την ένωση με τρόπο ώστε όλοι οι ομοιοπολικοί δεσμοί να μετατρέπονται σε κατευθυνόμενους ομοιοπολικούς δεσμούς. Λόγω της αστάθειας της νεοδημιουργηθείσας ένωσης, κάθε μόριο θα έχει μεγάλο αριθμό παλμών που θα βγαίνουν από αυτό και θα ταξιδεύουν σε άλλα μόρια χρησιμοποιώντας τους κατευθυνόμενους δεσμούς. Μια ώθηση μπορεί να ταξιδέψει χρησιμοποιώντας τον κατευθυνόμενο ομοιοπολικό δεσμό μόνο προς την κατεύθυνση του ίδιου του δεσμού.

Η αστάθεια της ένωσης ορίζεται ως ο μεγαλύτερος δυνατός αριθμός δεσμών που μπορεί να χρησιμοποιήσει ένας παλμός για να ταξιδέψει. Οι επιστήμονες θέλουν να κατευθύνουν τους ομοιοπολικούς δεσμούς της ένωσης με τρόπο ώστε η νεοδημιουργηθείσα ένωση να είναι όσο το δυνατόν πιο σταθερή. Με άλλα λόγια, στόχος τους είναι να δημιουργήσουν μια ένωση με την ελάχιστη μακρύτερη διαδρομή που μπορεί να ακολουθήσει ένας παλμός κατά τη διάρκεια του ταξιδιού της.

Βοηθήστε τους επιστήμονες να προσδιορίσουν την κατεύθυνση κάθε ομοιοπολικού δεσμού στην ένωση.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τον ακέραιο αριθμό ~N\;(2 \leq N \leq 100\,000)~. Κάθε μία από τις γραμμές ~N-1~ περιέχει τους ακέραιους αριθμούς ~a_i~ και ~b_i\;(1 \leq a_i,\;b_i \leq N)~ που δηλώνουν ότι τα μόρια ~a_i~ και ~b_i~ συνδέονται με ομοιοπολικό δεσμό.

Έξοδος

Τυπώστε ~N-1~ γραμμές, όπου κάθε γραμμή πρέπει να περιέχει 1 εάν ο ομοιοπολικός δεσμός πρόκειται να κατευθυνθεί από ~a_i~ στο ~b_i~, διαφορετικά περιέχει 0. Εάν υπάρχουν πολλές πιθανές λύσεις, τυπώστε οποιαδήποτε.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας τουλάχιστον ~30~% των συνολικών πόντων, θα έχει ~N \leq 20~.

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

input

3
1 2
2 3

output

1
0

Επεξήγηση του 1ου παραδείγματος:

Το παράδειγμα αντιστοιχεί στην αριστερή εικόνα από την εργασία. Η μεγαλύτερη διαδρομή που μπορεί να ακολουθήσει μια ώθηση είναι 1. Παρατηρήστε ότι το 0 1 είναι επίσης μια σωστή λύση.

input

4
2 1
1 3
4 1

output

0
1
0

Επεξήγηση του 2ου παραδείγματος:

Το παράδειγμα αντιστοιχεί στην δεξιά εικόνα από την εργασία.