\( \newcommand{\Z}{\mathbb{Z}} \newcommand{\val}{\textnormal{val}} \)

Let $G = (V,E)$ be an undirected graph, i.e., $E \subseteq {V \choose 2}$. A bridge is an edge $\{u,v\}$ that does not lie on a cycle.

This graph has three bridges: $\{1,2\}$, $\{3,10\}$, and $\{3,9\}$. Detecting whether $e = \{u,v\}$ should be easy: we could start a depth-first search at $u$, taking care never to take the edge $\{u,v\}$, and check whether we still reach $v$.

Problem Write a program that reads an undirected graph and outputs a list of bridges, sorted lexicographically.

Input: The first line contains two integers $n m$, the number of vertices and edges, respectively. The following $m$ lines contain two integers $1 \leq u, v \leq n$, separated by a space, meaning that $\{u,v\}$ is an edge in the graph.

Output: The list of bridges, sorted alphabetically, one edge per line, each line containing two integers $u v$ meaning that $\{u,v\}$ is a bridge; you should make sure that $u \lt v$ and that edges are sorted lexicographically, e.g., the set $\{\{2,1 \}, \{3, 10\}, \{9, 3\}\}$ should be output as in the order $(1,2), (3,9), (3, 10)$.

Sample Input

10 12
7 9
4 7
9 4
3 9
3 10
3 2
8 3
2 8
1 2
6 1
5 6
1 5

Sample Output

1 2 
3 9 
3 10
The running time of the above algorithm is quadratic: we need $O(m)$ time to decide whether $\{u,v\}$ is a bridge (using depth-first search, for example). Then we have to do this for every edge.

A Linear-Time Algorithm

Depth-first search builds a tree rooted at the starting node. In the above graph, when starting at vertex 8, we might get this tree:

Next to each vertex, let's write its depth in this tree:

Finally let's mark the edges that are not in the tree, and let's direct them from bottom to top, i.e., in the direction in which DFS wanted to take them when it discovered that the end vertex has already been visited:

This is now a directed graph $\vec{G}$: an orientation of $G$. Note that this orientation is not unique; a different order in which DFS visits the vertices might give us a different orientation. For each vertex $u$, we ask:

What is the minimum depth of a vertex reachable from $u$, following the edges in their direction in $\vec{G}$?

This number is always at most the depth of $u$ since $u$ itself is always reachable from $u$. We show these number below, in red:

There are two things two observe:

  1. We can compute the blue numbers (the depth) and the red numbers (minimum depth reachable in the oriented version) in linear time, in a single DFS run.
  2. An edge $\{u,v\}$ is a bridge if and only if $u$ and $v$ have different red numbers.

Problem Implement the above idea with the blue and red numbers to compute the set of bridges in linear time in a single DFS run. Your test cases can of course be identical to those of the previous problem.