The path

Problem Description

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 $\in$ $[1,n]$ It's guaranteed that there exists solution.

Input

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, $u_i$ and $v_i$ $(1 \leq u_i,v_i \leq n)$, indicating there is a link between nodes $u_i$ and $v_i$ and the direction is from $u_i$ to $v_i$. $\sum n \leq 3*10^5$,$\sum m \leq 6*10^5$ $1\leq n,m \leq 10^5$

Output

For each test case,print $m$ lines.The i-th line includes one integer:the length of edge from $u_i$ to $v_i$

Sample Input

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

Sample Output

1
2
2
1
4
4
1
1
3
4
4
4

Author

SXYZ

Source

2015 Multi-University Training Contest 8