Krasnal Przedsiębiorca chce otworzyć we Wrocławiu firmę organizującą wycieczki z przewodnikiem. Jego wycieczki będą odbywać się autobusem jadącym przez miasto, a za każdym razem, gdy autobus minie ciekawy zabytek, przez system nagłośnienia w autobusie zostanie odtworzony nagrany opis tego zabytku.

Krasnal przygotował mapę obejmującą $N$ zabytków, ponumerowanych od $1$ do $N$, oraz $M$ dwukierunkowych ulic, z których każda łączy pewną parę zabytków. Zaskakującą cechą jego mapy jest to, że z każdego zabytku wychodzi co najwyżej $7$ ulic. Każda wycieczka będzie ciągiem $3$ różnych zabytków, w którym każde dwa kolejne zabytki są połączone ulicą.

Teraz, przed wyborem tras wycieczek, krasnal musi przygotować nagrane opisy zabytków i zatrudnić profesjonalnych lektorów. Stać go na zatrudnienie tylko $4$ lektorów, a opis każdego zabytku może nagrać tylko raz, przy udziale jednego lektora. Przedsiębiorca obawia się jednak, że głos nawet najlepszego lektora może stać się monotonny dla słuchaczy, dlatego postanowił, że podczas żadnej możliwej wycieczki wszystkie $3$ opisy nie mogą być czytane przez tego samego lektora.

Krasnal nie zdecydował się jeszcze na żadną konkretną trasę wycieczki, a rezerwację studia nagraniowego ma już jutro. Pomóż mu przypisać lektorów do zabytków tak, aby w żadnej możliwej wycieczce wszystkie zabytki nie były czytane przez tego samego lektora.

Wejście

Pierwszy wiersz wejścia zawiera dwie oddzielone spacją liczby całkowite $N$ oraz $M$, oznaczające liczbę zabytków oraz liczbę ulic na mapie krasnala.

Kolejne $M$ wierszy opisuje ulice łączące zabytki, przy czym $i$-ty wiersz zawiera dwie oddzielone spacją liczby całkowite $a_i$ oraz $b_i$, oznaczające numery zabytków połączonych tą ulicą.

Wyjście

Wypisz jeden wiersz zawierający $N$ oddzielonych spacjami liczb całkowitych $c_1, \dots, c_N$, gdzie $c_i$ ($1 \le c_i \le 4$) oznacza identyfikator lektora, który powinien nagrać opis $i$-tego zabytku.

Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich. Możesz założyć, że w każdym teście istnieje jakieś rozwiązanie.

Ograniczenia

$1 \le N \le 10^6$

$1 \le M \le 3.5 \cdot 10^6$

$1 \le a_i, b_i \le N$

$a_i \neq b_i$

żadna ulica nie łączy zabytku z samym sobą,

żadna para zabytków nie jest połączona więcej niż jedną ulicą,

każdy zabytek jest incydentny z co najwyżej $7$ ulicami.

Przykłady

Wejście 1

3 3
1 2
2 3
3 1

Wyjście 1

2 1 1

Wejście 2

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

Wyjście 2

2 3 1 3 1 3 1 1