Zwerg der Unternehmer möchte in Breslau ein Stadtführungsunternehmen gründen. Seine Touren werden mit einem Bus durchgeführt, der durch die Stadt fährt, und jedes Mal, wenn der Bus an einer interessanten Sehenswürdigkeit vorbeifährt, wird über das Soundsystem des Busses eine aufgezeichnete Beschreibung dieser Sehenswürdigkeit abgespielt.

Der Zwerg hat eine Karte vorbereitet, die $N$ Sehenswürdigkeiten, nummeriert von $1$ bis $N$, sowie $M$ in beide Richtungen befahrbare Straßen umfasst, die jeweils ein Paar von Sehenswürdigkeiten verbinden. Ein überraschendes Merkmal seiner Karte ist, dass an jede Sehenswürdigkeit höchstens $7$ Straßen angrenzen. Jede Tour besteht aus einer Folge von $3$ verschiedenen Sehenswürdigkeiten, wobei je zwei aufeinanderfolgende Sehenswürdigkeiten durch eine Straße verbunden sind.

Bevor der Zwerg nun die Touren auswählt, muss er die aufgezeichneten Beschreibungen der Sehenswürdigkeiten vorbereiten und professionelle Sprecher engagieren. Er kann es sich nur leisten, $4$ Sprecher einzustellen, und er kann die Beschreibung für jede Sehenswürdigkeit nur einmal mit einem einzigen Sprecher aufnehmen. Der Unternehmer befürchtet jedoch, dass selbst die Stimme des besten Sprechers für das Publikum eintönig werden könnte, und hat daher entschieden, dass auf keiner möglichen Tour alle $3$ Beschreibungen vom selben Sprecher gesprochen werden dürfen.

Der Zwerg hat sich noch nicht für eine bestimmte Tour entschieden, und seine Reservierung für das Tonstudio ist bereits morgen. Hilf ihm, den Sehenswürdigkeiten Sprecher zuzuweisen, sodass auf keiner möglichen Tour alle Sehenswürdigkeiten vom selben Sprecher gesprochen werden.

Eingabe

Die erste Zeile der Eingabe enthält zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $M$, welche die Anzahl der Sehenswürdigkeiten und die Anzahl der Straßen auf der Karte des Zwergs angeben.

Die nächsten $M$ Zeilen beschreiben die Straßen, die die Sehenswürdigkeiten verbinden, wobei die $i$-te Zeile zwei durch Leerzeichen getrennte ganze Zahlen $a_i$ und $b_i$ enthält, welche die Nummern der durch diese Straße verbundenen Sehenswürdigkeiten bezeichnen.

Ausgabe

Gib eine einzige Zeile mit $N$ durch Leerzeichen getrennten ganzen Zahlen $c_1, \dots, c_N$ aus, wobei $c_i$ ($1 \le c_i \le 4$) die Kennung des Sprechers bezeichnet, der die Beschreibung der $i$-ten Sehenswürdigkeit aufnehmen soll.

Falls es mehrere Lösungen gibt, gib eine beliebige davon aus. Du kannst davon ausgehen, dass in jedem Testfall eine Lösung existiert.

Beschränkungen

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

keine Straße verbindet eine Sehenswürdigkeit mit sich selbst,

kein Paar von Sehenswürdigkeiten ist durch mehr als eine Straße verbunden,

an jede Sehenswürdigkeit grenzen höchstens $7$ Straßen an.

Beispiele

Eingabe 1

3 3
1 2
2 3
3 1

Ausgabe 1

2 1 1

Eingabe 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

Ausgabe 2

2 3 1 3 1 3 1 1