A sports camp has n children numbered 0 .. n-1. Each child will wear a red or a blue shirt. Coaches send statements one at a time: statements[i] = [a, b, s] means children a and b are on the same team if s == 0 and on different teams if s == 1.
A statement is accepted if it can hold together with every statement accepted before it; otherwise it is ignored for good. ([a, a, 1] is always ignored.)
After each statement (accepted or ignored), consider every shirt assignment that satisfies all accepted statements so far, and record the largest number of red shirts any of them uses. Return the list of recorded values, one per statement.
Examples
Input: n = 5, statements = [[0, 1, 1], [1, 2, 1], [3, 4, 1], [2, 3, 0], [0, 4, 0]]
Output: [4, 4, 3, 3, 3]
Explanation: after the fourth statement the groups are {0, 2, 3} against {1, 4},
so at most 3 reds. The fifth statement says 0 and 4 match, but 0 matches 3 and
3 differs from 4, so it is ignored.
Input: n = 2, statements = [[0, 1, 1], [0, 1, 0]]
Output: [1, 1]
Input: n = 3, statements = []
Output: []
Constraints
1 <= n <= 10**5,0 <= len(statements) <= 6 * 10**4,0 <= a, b < n- Target: about O((n + m) * alpha(n)) time. Recounting the groups after every statement is too slow.
Goals
- Keep, for every set, how many members sit on each side of its root
- Update a global answer in O(1) when two sets merge, flipping one side when needed
- Ignore a statement that contradicts the accepted ones without breaking the structure