給定一個包含 $n$ 個頂點與 $m$ 條邊的無向圖，你需要為每一條邊塗上 $1$ 到 $m$ 之間的顏色，使得對於任意頂點 $u$ 與任意顏色 $c$，連接至頂點 $u$ 且顏色為 $c$ 的邊至多只有 $2$ 條。

更正式地說，對於所有整數 $1 \le u \le n$，必須滿足以下限制：令 $d_u$ 為連接至頂點 $u$ 的邊數，令 $e_{u,1}, e_{u,2}, \dots, e_{u,d_u}$ 為這些邊，並令 $w(e)$ 為邊 $e$ 的顏色（顏色編號為 $1$ 到 $m$）。則對於所有整數 $1 \le c \le m$，$c$ 在序列 $w(e_{u,1}), w(e_{u,2}), \dots, w(e_{u,d_u})$ 中出現的次數至多為 $2$ 次。

令 $f_u$ 為連接至頂點 $u$ 的所有邊所使用的不同顏色數量。請找出一個塗色方案，使得 $\sum_{u=1}^{n} f_u$ 最小化。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，表示測試資料的組數。對於每組測試資料：

第一行包含兩個整數 $n$ 與 $m$ ($2 \le n \le 2 \times 10^5, 1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$)，分別表示圖中的頂點數與邊數。

接下來 $m$ 行，第 $i$ 行包含兩個整數 $u_i$ 與 $v_i$ ($1 \le u_i, v_i \le n$)，表示第 $i$ 條邊連接頂點 $u_i$ 與 $v_i$。

保證圖中沒有自我迴圈（self-loop）或重邊（multiple edges）。然而，給定的圖可能是不連通的。同時保證所有測試資料的 $n$ 之總和與 $m$ 之總和皆不超過 $2 \times 10^5$。

輸出格式

對於每組測試資料，輸出一行包含 $m$ 個整數 $w_1, w_2, \dots, w_m$ ($1 \le w_i \le m$)，並以空白分隔，其中 $w_i$ 為第 $i$ 條邊所塗的顏色。

若存在多種合法的答案，輸出其中任意一種即可。

範例

輸入格式 1

2
5 7
1 5
2 5
3 5
4 5
1 2
3 4
3 1
4 2
1 2
3 4

輸出格式 1

2 2 3 3 2 3 6
2 1