CodeParkA region has n villages numbered 1 to n. The plan was to connect them with exactly n - 1 two-way roads. Every village could reach every other, and there was no loop. A loop is a way to leave a village and come back without using a road twice.
The builders added one extra road. You get all n roads in roads, in the order they were built, as pairs [a, b].
Find the extra road. Taking it away must bring back the plan: every village still reachable, and no loop. Several roads might qualify. Then pick the one built latest, which is the one nearest the end of roads.
- Return the pair exactly as it appears in
roads(same order ofaandb). nis between 3 and 1,000.- No road joins a village to itself, and no two roads join the same pair of villages.
- The input always comes from a valid plan plus one extra road.
Input: roads = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]The three roads form a loop. Removing any one fixes it, and [2, 3] comes last.
Input: roads = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]The loop is 1-2-3-4-1. Road [1, 5] isn't part of it, so removing it would cut village 5 off.