Yrittäjäkääpiö haluaa perustaa matkaopasyrityksen Wrocławiin. Hänen kierroksensa toteutetaan kaupungin halki ajavalla bussilla, ja aina kun bussi ohittaa mielenkiintoisen maamerkin, bussin äänentoistojärjestelmästä soitetaan kyseisen maamerkin nauhoitettu kuvaus.

Kääpiö on laatinut kartan, joka sisältää $N$ maamerkkiä, numeroituina luvuilla $1$–$N$, sekä $M$ kaksisuuntaista katua, joista jokainen yhdistää kaksi maamerkkiä. Hänen karttansa yllättävä piirre on se, että jokaiseen maamerkkiin liittyy enintään $7$ katua. Jokainen kierros on $3$ eri maamerkin jono, jossa mitkä tahansa kaksi peräkkäistä maamerkkiä on yhdistetty kadulla.

Nyt ennen kierrosten valitsemista kääpiön täytyy valmistella maamerkkien nauhoitetut kuvaukset ja palkata ammattimaisia kertojia. Hänellä on varaa palkata vain $4$ kertojaa, ja hän voi nauhoittaa kunkin maamerkin kuvauksen vain kerran käyttäen yhtä kertojaa. Yrittäjä on kuitenkin huolissaan siitä, että jopa parhaan kertojan ääni voi käydä yleisölle yksitoikkoiseksi, joten hän on päättänyt, että millään mahdollisella kierroksella kaikkia $3$ kuvausta ei saa lukea sama kertoja.

Kääpiö ei ole vielä päättänyt mitään tiettyä kierrosta, ja hänen äänitysstudion varauksensa on huomenna. Auta häntä jakamaan kertojat maamerkeille siten, ettei millään mahdollisella kierroksella kaikkia maamerkkejä selosta sama kertoja.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $M$, jotka ilmaisevat maamerkkien lukumäärän ja katujen lukumäärän kääpiön kartalla.

Seuraavat $M$ riviä kuvaavat maamerkkejä yhdistävät kadut, missä $i$:s rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $a_i$ ja $b_i$, jotka ilmaisevat kyseisen kadun yhdistämien maamerkkien numerot.

Tuloste

Tulosta yksi rivi, jolla on $N$ välilyönnein erotettua kokonaislukua $c_1, \dots, c_N$, missä $c_i$ ($1 \le c_i \le 4$) ilmaisee sen kertojan tunnuksen, jonka tulee nauhoittaa $i$:nnen maamerkin kuvaus.

Jos ratkaisuja on useita, tulosta mikä tahansa niistä. Voit olettaa, että jokaisessa testitapauksessa on olemassa jokin ratkaisu.

Rajoitukset

$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$

mikään katu ei yhdistä maamerkkiä itseensä,

mitään maamerkkiparia ei yhdistä useampi kuin yksi katu,

jokaiseen maamerkkiin liittyy enintään $7$ katua.

Esimerkit

Syöte 1

3 3
1 2
2 3
3 1

Tuloste 1

2 1 1

Syöte 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

Tuloste 2

2 3 1 3 1 3 1 1