Skrivaca

Ο Marin και ο Luka παίζουν ένα δημοφιλές παιδικό παιχνίδι που λέγεται κρυφτό (Skrivaca). Παίζουν στο σπίτι τους που έχει ~n~ δωμάτια και ~m~ ζεύγη δωματίων συνδέονται με μια πόρτα. Τα δωμάτια έχουν δείκτες από το ~1~ έως το ~n~ και για κάθε ζεύγος δωματίων υπάρχει ένα μονοπάτι από το ένα στο άλλο.

Ο Luka έχει σκεφτεί μια στρατηγική για να κρύβεται: όταν ο Marin μπαίνει στο δωμάτιο ~v~, ο Luka θα κρύβεται στο δωμάτιο ~a_v~ . Στην αρχή του παιχνιδιού ο Marin διαλέγει το αρχικό του δωμάτιο ~v_0~ και ο Luka κρύβεται στο δωμάτιο ~a_v0~. Σε κάθε βήμα του παιχνιδιού, πρώτα ο Marin διαλέγει ένα δωμάτιο ~u~ το οποίο είναι δίπλα από το τρέχων δωμάτιο και μπαίνει σε αυτό. Μετά, ο Luka ξέρει ότι ο Marin είναι στο δωμάτιο ~u~ και σύμφωνα με την στρατηγική του κρύβεται στο δωμάτιο ~a_u~. Προσέξτε ότι ο Luka μπορεί να διαλέξει οποιοδήποτε μονοπάτι για να φτάσει στο δωμάτιο ~a_u~ και σε ένα βήμα του παιχνιδιού μπορεί να περάσει μέσα από έναν αυθαίρετο αριθμό δωματίων.

Ο Marin θα βρει τον Luka όταν και οι δυο τους βρίσκονται στο ίδιο δωμάτιο και εκείνη τη στιγμή τελειώνει το παιχνίδι.

Ο Marin έμαθε για την στρατηγική που ακολουθεί ο Luka και θέλει να καθορίσετε για κάθε αρχικό δωμάτιο αν ο Marin μπορεί να βρει τον Luka σε έναν πεπερασμένο αριθμό βημάτων και αν μπορεί, καθορίστε τα λιγότερα απαιτούμενα βήματα αν και οι δυο παίξουν με τον βέλτιστο τρόπο. (Ο Marin παίζει έτσι ώστε να βρει τον Luka στον λιγότερο αριθμό βημάτων και ο Luka έτσι ώστε να τον βρει ο Martin στον μεγαλύτερο αριθμό βημάτων).

Είσοδος

Στην πρώτη γραμμή υπάρχουν οι ακέραιοι ~n~, ~m~ (~1~ ~\le~ ~n~ ~\le~ ~2~ ~\cdot~ ~10^5~, ~n - 1~ ~\le~ ~m~ ~\le~ ~min~(~5~ ~\cdot~ ~10^5~, \(\fraq{1}{2}\)), τον αριθμό των δωματίων και τον αριθμό από τα ζεύγη συνδεδεμένων δωματίων.

Στη δεύτερη γραμμή υπάρχουν ~n~ ακέραιοι ~a_i~ (~1~ ~\le~ a_i~ ~\le~ ~n~), που περιγράφουν τη στρατηγική του Luka.

Στην ~i~-οστη από τις επόμενες ~m~ γραμμές υπάρχουν οι ακέραιοι ~x_i~, ~y_i~ (~1~ ~\le~ ~x_i~,~y_i~ ~\le~ ~n~, ~x_i~ ~\ne~ ~y_i~), που δηλώνουν ότι το δωμάτιο ~x_i~ και ~y_i~ ενώνονται. Μεταξύ κάθε ζεύγους δωματίων θα υπάρχει το πολύ ,μια σύνδεση.

Έξοδος

Στην πρώτη και μοναδική γραμμή τυπώστε ~n~ αριθμούς, όπου ο ~i~-οστος αριθμός δηλώνει τον μικρότερο αριθμό βημάτων που χρειάζεται ο Marin για να βρει τον Luka αν ο Marin ξεκινήσει στο δωμάτιο ~i~, ή ~-1~ αν ο Marin δεν μπορεί να βρει τον Luka.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~n~ ~\le~ ~1\,000~, ~m~ ~\le~ ~2\,000~
2	25	~m = n - 1~
3	30	Η στρατηγική του Luka θα είναι τέτοια ώστε δεν θα προσπαθήσει ποτέ να κρυφτεί στο δωμάτιο που βρίσκεται εκείνη τη στιγμή ο Marin ή σε κάποιο διπλανό του και η διάταξη του σπιτιού θα είναι τέτοια ώστε το παιχνίδι να μπορεί να τελειώσει στο πολύ ~5~ διαφορετικά δωμάτια άσχετα από την στρατηγική του Luka
4	40	Κανένας επιπλέον περιορισμός.

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

input

4 4
3 4 1 2
1 2
2 3
3 4
4 1

output

-1 -1 -1 -1

input

8 9
2 3 2 1 6 5 6 7
1 2
1 3
2 4
3 4
4 5
4 6
6 7
5 7
4 8

output

1 2 2 2 1 1 1 1

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

Ο Marin μπαίνει στο δωμάτιο ~8~ από το δωμάτιο ~4~ στο πρώτο βήμα και στο δεύτερο πηγαίνει πίσω στο δωμάτιο ~4~. Ο Luka πρέπει να περάσει από το δωμάτιο ~4~ για να πάει από το δωμάτιο ~7~ στο δωμάτιο ~1~ οπότε ο Marin μπορεί να βρει τον Luka σε ~2~ βήματα.

input

9 8
1 9 1 1 1 9 9 9 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

output

0 1 1 2 1 1 2 1 1