Redundant link in a network

Scenario

You work on a maps app. Survey teams report roads between intersections, one road at a time. The intersections are numbered 0 to n - 1, and a road works in both directions.

A road is redundant when the two intersections at its ends were already joined by earlier reports, directly or through other intersections. It closes a loop, and the map team wants to review it. Your team lead says: "Tell me the first redundant road in the list."

Your task

Write first_redundant_link(n, roads).

n is the number of intersections.
roads[i] = [a, b] is the road reported at position i, counting from 0. It joins intersections a and b.
Return the position of the first redundant road. Return -1 when no road is redundant.

A road that is listed a second time is redundant, because its two ends are already joined.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 5, roads = [[0, 1], [1, 2], [3, 4], [2, 0], [2, 3]]
Output: 3

Keep the intersections in groups. A road is redundant when its two ends are already in one group.

Position	Road	Already joined?	Groups after
start			{0} {1} {2} {3} {4}
0	[0, 1]	no	{0, 1} {2} {3} {4}
1	[1, 2]	no	{0, 1, 2} {3} {4}
2	[3, 4]	no	{0, 1, 2} {3, 4}
3	[2, 0]	yes: 0, 1, 2 are one group	unchanged

Position 3 is the first redundant road, so the answer is 3. The later road [2, 3] does not matter.

Example 2#

text2 lines

Input:  n = 4, roads = [[0, 1], [1, 2], [2, 3]]
Output: -1

Every road joins two groups that were apart. No road is redundant.

Example 3#

text2 lines

Input:  n = 3, roads = [[0, 1], [0, 1]]
Output: 1

The same road appears twice. At position 1, intersections 0 and 1 are already joined, so it is redundant.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(roads) ≤ 200,000, and every row is [a, b] with 0 ≤ a, b < n and a ≠ b

What does n ≤ 100000 tell you?

There can be 100,000 intersections and 200,000 roads. For each road, a search over the earlier roads costs about n + m. All the roads then cost m × (n + m): 60 billion steps. A union-find structure answers "are they already joined" in almost constant time, so the whole scan takes about 300,000 steps.

Scenario

You work on a maps app. Survey teams report roads between intersections, one road at a time. The intersections are numbered 0 to n - 1, and a road works in both directions.

Your task

Write first_redundant_link(n, roads).

n is the number of intersections.
roads[i] = [a, b] is the road reported at position i, counting from 0. It joins intersections a and b.
Return the position of the first redundant road. Return -1 when no road is redundant.

A road that is listed a second time is redundant, because its two ends are already joined.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 5, roads = [[0, 1], [1, 2], [3, 4], [2, 0], [2, 3]]
Output: 3

Keep the intersections in groups. A road is redundant when its two ends are already in one group.

Position	Road	Already joined?	Groups after
start			{0} {1} {2} {3} {4}
0	[0, 1]	no	{0, 1} {2} {3} {4}
1	[1, 2]	no	{0, 1, 2} {3} {4}
2	[3, 4]	no	{0, 1, 2} {3, 4}
3	[2, 0]	yes: 0, 1, 2 are one group	unchanged

Position 3 is the first redundant road, so the answer is 3. The later road [2, 3] does not matter.

Example 2#

text2 lines

Input:  n = 4, roads = [[0, 1], [1, 2], [2, 3]]
Output: -1

Every road joins two groups that were apart. No road is redundant.

Example 3#

text2 lines

Input:  n = 3, roads = [[0, 1], [0, 1]]
Output: 1

The same road appears twice. At position 1, intersections 0 and 1 are already joined, so it is redundant.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(roads) ≤ 200,000, and every row is [a, b] with 0 ≤ a, b < n and a ≠ b

What does n ≤ 100000 tell you?