n nodes (numbered 1 to n) is stored as directed links [u, v], where u is the parent of v. The root has no parent, every other node has exactly one, and every node can be reached from the root.
By mistake, one extra directed link between two different nodes, one that did not exist before, was added to the list links. Now there are exactly n links.
Find a link whose removal turns the graph back into a rooted tree on all n nodes. If several links qualify, return the one that appears last in links.links=[[2, 3], [1, 2], [3, 1], [2, 4]] → [3, 1]
Every node has a parent, so the extra link points into the root and closes the cycle 1 → 2 → 3 → 1. Any link of the cycle can go; the last one in the list is [3, 1], leaving 1 as the root.
links=[[1, 2], [1, 3], [3, 4], [2, 4]] → [2, 4]
Node 4 has two parents. Either [3, 4] or [2, 4] can be removed, so take the one that comes later in the list.
links=[[4, 2], [1, 4], [2, 3], [3, 4]] → [3, 4]
links is a rooted tree plus one extra linklinks=[[2, 3], [1, 2], [3, 1], [2, 4]]
[3, 1]
Run checks the first 3 tests in your browser. Submit checks all 55 tests on the server, hidden ones included.