One Cable Too Many

An office network had n computers, numbered 0 to n - 1, wired as a tree: n - 1 two-way cables, with exactly one route of cables between any two computers. Then a technician plugged in one more cable between two different computers, and now the network has a loop.

cables lists all n cables as pairs [a, b], in the order they were plugged in, so n is len(cables). Write extra_cable(cables) that returns a cable you can unplug to turn the network back into a tree. Any cable on the loop would do, so return the one that comes last in cables, as the same [a, b] list it appears as there.

Examples

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

In the second network the loop runs from computer 1 to 2 to 3 and back to 1. Unplugging any of its three cables leaves a tree, and [1, 3] is the last of them in the list.

Constraints

• 2 <= n <= 20,000.
• The extra cable may join two computers that already had a cable between them. Then those two cables form the loop.

Note

• The loop can pass through all 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.