8605: GRL_3_B : Bridges
[Creator : ]
Description
Find bridges of an undirected graph G(V,E).
A bridge (also known as a cut-edge) is an edge whose deletion increase the number of connected components.
Input
In the first line, two integers |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.
In the following |E| lines, two integers $s_i$ and $t_i$ represent source and target verticess of $i$-th edge (undirected).
Output
A list of bridges of the graph ordered by name. For each bridge, names of its end-ponints, source and target (source < target), should be printed separated by a space. The sources should be printed ascending order, then the target should also be printed ascending order for the same source.
Constraints
1 ≤ |V| ≤ 100,000
0 ≤ |E| ≤ 100,000
The graph is connected
There are no parallel edges
There are no self-loops
0 ≤ |E| ≤ 100,000
The graph is connected
There are no parallel edges
There are no self-loops
Sample 1 Input
4 4
0 1
0 2
1 2
2 3
Sample 1 Output
2 3
Sample 2 Input
5 4
0 1
1 2
2 3
3 4
Sample 2 Output
0 1
1 2
2 3
3 4