1304: triangle

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