#196HardGraphs· Bridges (Tarjan Low-Link)

Critical Network Links

A data-centre network has `n` routers numbered `0` to `n - 1` connected by bidirectional links. A link is **critical** if removing it increases the number of groups of routers that can still reach each other (so that some pair of routers that could communicate before no longer can). Given the list of links, return every critical link as a pair `[a, b]` with `a < b`. List the pairs in ascending order (by `a`, then by `b`). The network does not have to be connected, and no pair of routers is joined by more than one link.

Input format

`n`: number of routers; `links`: an array of pairs `[u, v]` naming the routers each link joins.

Output format

An array of the critical links as pairs `[a, b]` with `a < b`, sorted ascending.

Examples

Input: n = 4, links = [[0, 1], [1, 2], [2, 0], [1, 3]]

Output: [[1, 3]]

Routers 0, 1, 2 form a triangle, so any one of those links can fail without disconnecting anything. The link 1-3 is the only way to reach router 3.

Input: n = 2, links = [[0, 1]]

Output: [[0, 1]]

The only link is critical: removing it separates the two routers.

Input: n = 3, links = [[0, 1], [1, 2], [2, 0]]

Output: []

In a cycle every link has an alternative route, so no link is critical.

Constraints

1 <= n <= 10^5
0 <= links.length <= 2 * 10^5
0 <= u, v < n and u != v
No two links join the same pair of routers.

Study first

Graphs and Traversal: BFS and DFS

#graph
#depth-first-search
#bridges
#tarjan
#low-link