CRB and Graph

A connected, undirected graph of N vertices and M edges is given to CRB.
A pair of vertices (u, v) (u < v) is called critical for edge e if and only if u and v become disconnected by removing e.
CRB’s task is to find a critical pair for each of M edges. Help him!

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, M denoting the number of vertices and the number of edges.
Each of the next M lines contains a pair of integers a and b, denoting an undirected edge between a and b.
1 ≤ T ≤ 12
1 ≤ N, M ≤ 105
1 ≤ a, b ≤ N
All given graphs are connected.
There are neither multiple edges nor self loops, i.e. the graph is simple.

For each test case, output M lines, i-th of them should contain two integers u and v, denoting a critical pair (u, v) for the i-th edge in the input.
If no critical pair exists, output "0 0" for that edge.
If multiple critical pairs exist, output the pair with largest u. If still ambiguous, output the pair with smallest v.

2
3 2
3 1
2 3
3 3
1 2
2 3
3 1

1 2
2 3
0 0
0 0
0 0

2015 Multi-University Training Contest 10