企業家矮人想要在弗羅茨瓦夫開展一項旅遊導覽業務。他的旅遊團將乘坐巴士穿過城市，每當巴士經過一個有趣的景點時，車載音響系統就會播放該景點的錄製解說。

矮人準備了一張地圖，其中包含 $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