$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$) が与えられます。各テストケースは以下の形式で与えられます。

最初の行には、2 つの整数 $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$ 行目には、2 つの整数 $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$) をスペース区切りで 1 行に出力してください。ここで $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