You have a connected directed graph.Let d(x) be the length of the shortest path from 1 to x.Specially d(1)=0.A graph is good if there exist x satisfy d(1)<d(2)<....d(x)>d(x+1)>...d(n).Now you need to set the length of every edge satisfy that the graph is good.Specially,if d(1)<d(2)<..d(n),the graph is good too.
The length of one edge must ∈ [1,n]
It's guaranteed that there exists solution.
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m,the number of vertexs and the number of edges.Next m lines contain two integers each, ui and vi (1≤ui,vi≤n), indicating there is a link between nodes ui and vi and the direction is from ui to vi.
∑n≤3∗105,∑m≤6∗105
1≤n,m≤105
For each test case,print m lines.The i-th line includes one integer:the length of edge from ui to vi
2 4 6 1 2 2 4 1 3 1 2 2 2 2 3 4 6 1 2 2 3 1 4 2 1 2 1 2 1
1 2 2 1 4 4 1 1 3 4 4 4