Athafnadvergurinn vill stofna fyrirtæki í kringum leiðsögn ferðamanna í Wrocław. Ferðirnar hans verða farnar á rútu sem ekur um borgina, og í hvert sinn sem rútan fer fram hjá áhugaverðu kennileiti verður upptekin lýsing á því kennileiti spiluð í hljóðkerfi rútunnar.

Dvergurinn hefur útbúið kort sem inniheldur $N$ kennileiti, númeruð frá $1$ til $N$, og $M$ tvístefnugötur, þar sem hver gata tengir saman par af kennileitum. Óvæntur eiginleiki kortsins hans er að við hvert kennileiti liggja í mesta lagi $7$ götur. Hver ferð verður runa af $3$ ólíkum kennileitum, þar sem hver tvö samliggjandi kennileiti í rununni eru tengd með götu.

Núna, áður en ferðirnar eru valdar, þarf dvergurinn að undirbúa uppteknu lýsingarnar á kennileitunum og ráða atvinnusögumenn. Hann hefur aðeins efni á að ráða $4$ sögumenn, og hann getur aðeins tekið upp lýsinguna fyrir hvert kennileiti einu sinni, með einum sögumanni. Athafnadvergurinn hefur hins vegar áhyggjur af því að jafnvel rödd besta sögumannsins geti orðið einhæf fyrir áheyrendur, svo hann hefur ákveðið að í engri mögulegri ferð megi allar $3$ lýsingarnar vera lesnar af sama sögumanninum.

Dvergurinn hefur enn ekki ákveðið neina tiltekna ferð, og bókunin hans í hljóðverinu er á morgun. Hjálpaðu honum að úthluta sögumönnum á kennileitin þannig að þau verði ekki öll lesin af sama sögumanninum í neinni mögulegri ferð.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $N$ og $M$ aðskildar með bili, sem tákna fjölda kennileita og fjölda gatna á korti dvergsins.

Næstu $M$ línur lýsa götunum sem tengja kennileitin, þar sem $i$-ta línan inniheldur tvær heiltölur $a_i$ og $b_i$ aðskildar með bili sem tákna númer kennileitanna sem tengjast með þessari götu.

Úttak

Prentaðu eina línu með $N$ heiltölum $c_1, \dots, c_N$ aðskildum með bilum, þar sem $c_i$ ($1 \le c_i \le 4$) táknar auðkenni sögumannsins sem á að taka upp lýsinguna á $i$-ta kennileitinu.

Ef til eru margar lausnir skaltu prenta hverja sem er þeirra. Þú getur gert ráð fyrir að í hverju prófunartilviki sé til einhver lausn.

Takmarkanir

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

engin gata tengir nokkurt kennileiti við sjálft sig,

ekkert par af kennileitum er tengt með fleiri en einni götu,

við hvert kennileiti liggja í mesta lagi $7$ götur.

Dæmi

Inntak 1

3 3
1 2
2 3
3 1

Úttak 1

2 1 1

Inntak 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

Úttak 2

2 3 1 3 1 3 1 1