odd doctor 已更新

CRB and Graph

Time Limit
4s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(1/1)
Description:

A connected, undirected graph of N vertices and M edges is given to CRB.
A pair of vertices (uv) (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!

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 NM 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 ≤ NM ≤ 105
1 ≤ ab ≤ N
All given graphs are connected.
There are neither multiple edges nor self loops, i.e. the graph is simple.

Output:

For each test case, output M lines, i-th of them should contain two integers u and v, denoting a critical pair (uv) 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.

Sample Input:
2
3 2
3 1
2 3
3 3
1 2
2 3
3 1
Sample Output:
1 2
2 3
0 0
0 0
0 0
Source:

2015 Multi-University Training Contest 10


Submit