26844번 - Hydrorozgrywka 다국어

문제

Ekipy hydrauliczne Bajtazara i Bajtoniego wygrały przetarg na doprowadzenie wody do Bajtołów Dolnych. Sieć drogowa w tym mieście składa się z n skrzyżowań połączonych m odcinkami dróg. Z każdego skrzyżowania można dojechać do każdego innego skrzyżowania za pomocą sieci dróg. Pod każdym odcinkiem drogi należy zakopać rurę wodociągową.

Aby urozmaicić sobie pracę, Bajtazar i Bajtoni postanowili zagrać w grę. Na początek ekipy obu bohaterów stają na jednym ze skrzyżowań. Przez całą grę obie ekipy będą podążać razem. Gracze wykonują ruchy na przemian, począwszy od Bajtazara. W swoim ruchu gracz wskazuje swojej ekipie odcinek drogi (pod którym jeszcze nie ma rury) wychodzący ze skrzyżowania, na którym znajdują się obie ekipy. Ekipa gracza zakopuje rurę pod tym odcinkiem drogi i następnie obie ekipy przemieszczają się do drugiego ze skrzyżowań, które łączy ten odcinek.

Gracz, który nie może wykonać ruchu, przegrywa i za karę jego ekipa musi zakopać rury pod pozostałymi odcinkami dróg. Bajtazar zastanawia się, od którego skrzyżowania może zacząć się gra, aby był w stanie wygrać niezależnie od ruchów Bajtoniego. Poprosił Cię o pomoc w ustaleniu listy takich skrzyżowań. Dodatkowo zauważył, że sieć drogowa w Bajtołach ma ciekawą własność: wyjeżdżając ze środka dowolnego odcinka drogi na dokładnie jeden sposób możemy zrobić „pętlę” i wrócić do punktu wyjścia, jeśli nigdy nie zawracamy i nie odwiedzamy żadnego skrzyżowania dwukrotnie.

입력

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite n i m oddzielone pojedynczym odstępem, oznaczające liczbę skrzyżowań i liczbę odcinków dróg. Skrzyżowania numerujemy liczbami od 1 do n. Kolejne m wierszy opisuje sieć drogową: każdy z nich zawiera dwie liczby całkowite a, b (1 ≤ a, b ≤ n, a ≠ b) oddzielone pojedynczym odstępem, oznaczające, że skrzyżowania o numerach a i b są połączone odcinkiem drogi. Możesz założyć, że żadne dwa skrzyżowania nie są połączone więcej niż jednym odcinkiem drogi.

출력

Na standardowe wyjście należy wypisać dokładnie n wierszy: i-ty z nich ma zawierać liczbę 1, jeśli Bajtazar może wygrać, gdy gra zacznie się ze skrzyżowania numer i; w przeciwnym wypadku ma zawierać liczbę 2.

제한

• 3 ≤ n, m ≤ 500 000

힌트