Given an undirected graph with $n$ vertices and $m$ edges, you need to paint each edge with one of the $m$ colors, such that for any vertex $u$ and any color $c$, at most 2 edges connecting vertex $u$ are painted with color $c$.

More formally, for all integers $1 \le u \le n$, the following constraint must be satisfied: let $d_u$ be the number of edges connecting vertex $u$, let $e_{u,1}, e_{u,2}, \dots, e_{u,d_u}$ be these edges, and let $w(e)$ be the color of edge $e$ (colors are numbered from $1$ to $m$). Then, for all integers $1 \le c \le m$, $c$ appears at most twice in the sequence $w(e_{u,1}), w(e_{u,2}), \dots, w(e_{u,d_u})$.

Let $f_u$ be the number of different colors on all edges connecting vertex $u$. Find a way to paint the edges and minimize $\sum_{u=1}^n f_u$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \times 10^5$, $1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$), indicating the number of vertices and the number of edges in the graph.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), indicating that the $i$-th edge connects vertices $u_i$ and $v_i$.

It’s guaranteed that there are no self loops or multiple edges in the graph. However, the given graph might not be connected. It’s also guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $2 \times 10^5$.

Output

For each test case, output one line containing $m$ integers $w_1, w_2, \dots, w_m$ ($1 \le w_i \le m$) separated by a space, where $w_i$ is the color painted on the $i$-th edge.

If there are multiple valid answers, you can output any of them.

Examples

Input 1

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

Output 1

2 2 3 3 2 3 6
2 1