Critical Cables

A data centre has n computers, numbered 0 to n - 1, and cables lists its two-way cables as pairs [a, b]. A cable is critical if unplugging it cuts some pair of computers off from each other: they were connected before, directly or through other computers, and they are not connected afterwards.

Write critical_cables(n, cables) that returns every critical cable as a tuple (a, b) with a < b, in a sorted list.

Examples

critical_cables(4, [[0, 1], [1, 2], [2, 0], [1, 3]])  # returns [(1, 3)]
critical_cables(5, [[0, 1], [1, 2], [3, 4]])  # returns [(0, 1), (1, 2), (3, 4)]
critical_cables(2, [[0, 1], [1, 0]])  # returns []

In the first network, computers 0, 1 and 2 form a loop, so any one of its cables can go and the other two still connect them, but computer 3 hangs on the cable to computer 1 alone. In the last network two cables join the same two computers, so neither of them is critical.

Constraints

• 1 <= n <= 20,000, with up to 40,000 cables. A cable joins two different computers, and the network may already be in several separate pieces.

Note

• The network can be a single chain of 20,000 computers. Python stops recursion at about 1,000 levels, so a recursive search has to be rewritten with a stack of your own.