Dvergen Entreprenøren ønsker å starte en turistguidevirksomhet i Wrocław. Turene hans vil foregå med buss som kjører gjennom byen, og hver gang bussen passerer et interessant landemerke, vil en innspilt beskrivelse av dette landemerket spilles av over lydanlegget i bussen.

Dvergen har laget et kart som inneholder $N$ landemerker, nummerert fra $1$ til $N$, og $M$ toveis gater, som hver forbinder et par landemerker. Et overraskende trekk ved kartet hans er at hvert landemerke er tilknyttet høyst $7$ gater. Hver tur vil være en sekvens av $3$ forskjellige landemerker, der hver to påfølgende landemerker er forbundet med en gate.

Nå, før han velger turene, må dvergen forberede de innspilte beskrivelsene av landemerkene og leie inn profesjonelle fortellere. Han har bare råd til å leie inn $4$ fortellere, og han kan spille inn beskrivelsen for hvert landemerke bare én gang, ved hjelp av én enkelt forteller. Entreprenøren er imidlertid bekymret for at selv den beste fortellerens stemme kan bli monoton for publikum, så han har bestemt at i enhver mulig tur kan ikke alle de $3$ beskrivelsene leses av samme forteller.

Dvergen har ennå ikke bestemt seg for noen spesifikk tur, og reservasjonen hans i innspillingsstudioet er i morgen. Hjelp ham med å tildele fortellere til landemerkene slik at de ikke blir lest av samme forteller i noen mulig tur.

Inndata

Den første linjen i inndataen inneholder to mellomromseparerte heltall $N$ og $M$, som angir antallet landemerker og antallet gater på dvergens kart.

De neste $M$ linjene beskriver gatene som forbinder landemerkene, der den $i$-te linjen inneholder to mellomromseparerte heltall $a_i$ og $b_i$ som angir numrene på landemerkene som er forbundet med denne gaten.

Utdata

Skriv ut én enkelt linje med $N$ mellomromseparerte heltall $c_1, \dots, c_N$, der $c_i$ ($1 \le c_i \le 4$) angir ID-en til fortelleren som skal spille inn beskrivelsen av det $i$-te landemerket.

Hvis det finnes mange løsninger, kan du skrive ut hvilken som helst av dem. Du kan anta at det i hvert testtilfelle finnes en løsning.

Begrensninger

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

ingen gate forbinder noe landemerke med seg selv,

intet par av landemerker er forbundet med mer enn én gate,

hvert landemerke er tilknyttet høyst $7$ gater.

Eksempler

Inndata 1

3 3
1 2
2 3
3 1

Utdata 1

2 1 1

Inndata 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

Utdata 2

2 3 1 3 1 3 1 1