In an unidirectional graph containing no loops or multiple edges, we call an edge e's exp value exp(e) as the number of three-edge rings that contain edge e. In addition, we call a graph G(V,E)'s nice value nice(E)=min(exp(e),e∈E), and an edge e's nice value nice(e)=(max(nice(H)),e∈H and H is subgraph of G). Now with a given unidirectional graph without loops or multiple edges, you are required to calculate each edge's nice value.
The first line contains only one integer T(1≤T≤10), which indicates the number of test cases.
For each case:
- The first line contains two integers n,m(0≤n≤2000,0≤m≤5000), indicating the number of vertices and the number of edges, respectively;
- In the next m lines, each line contains two integers u,v(1≤u,v≤n), indicating there is an edge between vertex u and vertex v.
For each test case, output m lines, where the ith lines contains an integer indicating the nice value of the ith edge.
1 3 3 1 2 2 3 1 3
1 1 1