E. Colorful Graph
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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}, \cdots, 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}), \cdots, 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\limits_{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, \cdots, 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.

Example
Input
2
5 7
1 5
2 5
3 5
4 5
1 2
3 4
3 1
4 2
1 2
3 4
Output
2 2 3 3 2 3 6
2 1