triangle

Time Limit: 2000 ms Memory Limit: 131072 KiB

Problem Description

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),eE), and an edge e's nice value nice(e)=(max(nice(H)),eH 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.

Input

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,vn), indicating there is an edge between vertex u and vertex v.

Output

For each test case, output m lines, where the ith lines contains an integer indicating the nice value of the ith edge.

Sample Input

1
3 3
1 2
2 3
1 3

Sample Output

1
1
1

Hint

Source

“浪潮杯”山东省第八届ACM大学生程序设计竞赛(感谢青岛科技大学)