给定一个包含 $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})$ 中最多出现两次。

设 $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