First Contradiction

Medium · union find

A quiz night has n players, numbered 0 to n - 1. Every player is on one of two teams, the Owls or the Foxes, but nobody remembers who is on which.

Witnesses make claims, one after another, in the order of the list claims. Each claim is [a, b, k] about two different players:

k = 0 means players a and b are on the same team.
k = 1 means players a and b are on different teams.

A set of claims is consistent if the players can be split into the two teams so that every claim in the set is true. A team may even end up empty.

Find the smallest number t such that the first t claims cannot all be true together. Return t, counting claims from 1. If all the claims together are consistent, return -1.

Examples

Example 1

Input: n = 4, claims = [[0, 1, 0], [1, 2, 1], [2, 3, 0], [0, 3, 0]]

Output: 4

The first three claims put players 0 and 1 together, 2 and 3 together, and the two pairs on opposite teams. The fourth claim says 0 and 3 are together, which is impossible.

Example 2

Input: n = 3, claims = [[0, 1, 1], [1, 2, 1], [0, 2, 0]]

Output: -1

Player 1 is on the other team from both 0 and 2, so 0 and 2 share a team. The last claim agrees.

Example 3

Input: n = 3, claims = [[0, 1, 0], [1, 0, 1]]

Output: 2

The second claim directly contradicts the first.

Constraints

2 <= n <= 10^5
0 <= len(claims) <= 10^5
claims[i] has exactly three numbers: a, b and k
0 <= a, b < n and a != b
k is 0 or 1