企業家矮人想喺弗羅茨瓦夫開辦一間旅遊導賞公司。佢嘅導賞團將會搭巴士穿過城市，每當巴士經過一個有趣嘅景點時，車上嘅音響系統就會播放嗰個景點嘅錄音介紹。

呢位矮人準備咗一張地圖，入面包含 $N$ 個景點（編號由 $1$ 到 $N$）同埋 $M$ 條雙向街道，每條街道連接一對景點。佢張地圖有一個驚人嘅特點：每個景點最多同 $7$ 條街道相連。每條導賞路線都係由 $3$ 個唔同景點組成嘅序列，其中每兩個連續嘅景點之間都有一條街道相連。

而家，喺揀定導賞路線之前，矮人需要準備好各個景點嘅錄音介紹並聘請專業旁白員。佢只係請得起 $4$ 名旁白員，而且每個景點嘅介紹只可以錄製一次，由單一一位旁白員負責。不過，企業家擔心就算係最好嘅旁白員，把聲聽得多都會令聽眾覺得單調，所以佢決定喺任何可能嘅導賞路線入面，全部 $3$ 段介紹都唔可以由同一位旁白員錄製。

矮人仲未決定好任何具體嘅導賞路線，但佢預約嘅錄音室聽日就要用喇。請幫佢為各個景點分配旁白員，使得喺任何可能嘅導賞路線入面，呢啲景點都唔會全部由同一位旁白員負責旁白。

輸入格式

輸入嘅第一行包含兩個以空格分隔嘅整數 $N$ 同 $M$，分別表示矮人地圖上嘅景點數量同埋街道數量。

接落嚟嘅 $M$ 行描述連接各個景點嘅街道，其中第 $i$ 行包含兩個以空格分隔嘅整數 $a_i$ 同 $b_i$，表示呢條街道所連接嘅兩個景點編號。

輸出格式

輸出一行，包含 $N$ 個以空格分隔嘅整數 $c_1, \dots, c_N$，其中 $c_i$ ($1 \le c_i \le 4$) 表示應該為第 $i$ 個景點錄製介紹嘅旁白員編號。

如果存在多種解，輸出其中任意一種即可。你可以假設喺每個測試點入面都至少存在一種解。

數據範圍

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

冇任何街道將一個景點連接去佢自己，

冇任何一對景點之間由多過一條街道連接，

每個景點最多同 $7$ 條街道相連。

範例

輸入 1

3 3
1 2
2 3
3 1

輸出 1

2 1 1

輸入 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

輸出 2

2 3 1 3 1 3 1 1