$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$ を最小化する方法を求めよ。

入力

入力は複数のテストケースからなる。1 行目にはテストケースの数 $T$ ($1 \le T \le 10^4$) が与えられる。各テストケースは以下の形式である。

1 行目には 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

2 2 3 3 2 3 6
2 1