Dvärgen Entreprenören vill starta en turistguideverksamhet i Wrocław. Hans turer kommer att genomföras med buss som kör genom staden, och varje gång bussen passerar ett intressant landmärke kommer en inspelad beskrivning av detta landmärke att spelas upp i bussens ljudsystem.

Dvärgen har förberett en karta som innehåller $N$ landmärken, numrerade från $1$ till $N$, och $M$ dubbelriktade gator, som var och en förbinder ett par landmärken. En överraskande egenskap hos hans karta är att varje landmärke gränsar till högst $7$ gator. Varje tur kommer att vara en sekvens av $3$ olika landmärken, där varje par av på varandra följande landmärken förbinds av en gata.

Nu, innan han väljer turerna, behöver dvärgen förbereda de inspelade beskrivningarna av landmärkena och anlita professionella berättare. Han har bara råd att anlita $4$ berättare, och han kan spela in beskrivningen för varje landmärke endast en gång, med en enda berättare. Entreprenören är dock orolig för att även den bästa berättarens röst kan bli monoton för publiken, så han har bestämt att i varje möjlig tur får inte alla $3$ beskrivningarna läsas av samma berättare.

Dvärgen har ännu inte bestämt sig för någon specifik tur, och hans bokning av inspelningsstudion är imorgon. Hjälp honom att tilldela berättare till landmärkena så att de inte läses av samma berättare i någon möjlig tur.

Indata

Den första raden i indatan innehåller två blankstegsseparerade heltal $N$ och $M$, som anger antalet landmärken och antalet gator på dvärgens karta.

De följande $M$ raderna beskriver gatorna som förbinder landmärkena, där den $i$-te raden innehåller två blankstegsseparerade heltal $a_i$ och $b_i$ som anger numren på de landmärken som förbinds av denna gata.

Utdata

Skriv ut en enda rad med $N$ blankstegsseparerade heltal $c_1, \dots, c_N$, där $c_i$ ($1 \le c_i \le 4$) anger id-numret för den berättare som ska spela in beskrivningen av det $i$-te landmärket.

Om det finns många lösningar, skriv ut vilken som helst av dem. Du kan anta att det i varje testfall finns någon lösning.

Begränsningar

$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 gata förbinder något landmärke med sig självt,

inget par av landmärken förbinds av mer än en gata,

varje landmärke gränsar till högst $7$ gator.

Exempel

Indata 1

3 3
1 2
2 3
3 1

Utdata 1

2 1 1

Indata 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