給定一個包含 $n$ 個頂點與 $m$ 條邊的無向圖，你需要為每條邊塗上 $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$。

保證圖中沒有自環或重邊。圖可能不連通。同時保證所有測試資料的 $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