1023. Allies and Enemies in One Structure

n players are split into two sides, and you are told m claims in order. Each claim is one of

1 u v u and v are on the SAME side 2 u v u and v are on OPPOSITE sides

A claim is FALSE when it contradicts the claims accepted before it. A false claim is thrown away and the rest carry on as though it had never been made.

Print how many of the m claims are false.

3 players, claims 2 1 2 / 2 2 3 / 2 1 3 -> 1 3 players, claims 2 1 2 / 2 2 3 / 1 1 3 -> 0 2 players, claim 2 1 1 -> 1 4 players, claims 1 1 2 / 2 2 3 / 1 3 4 / 1 1 4 -> 1

The first two examples are worth reading together. Once 1 opposes 2 and 2 opposes 3, players 1 and 3 are forced onto the SAME side, so "1 opposes 3" is false and "1 and 3 are the same" is true. Neither fact was stated; both follow.

## What most people try first

After each claim, two-colour the whole set of accepted claims from scratch and see whether it still works. That is O(n + m) per claim, so O(m(n + m)) overall.

## Double the elements

Give every player TWO elements: u standing for "the side u is on", and u + n standing for "the other side". Then the two kinds of claim both become plain merges:

same(u, v): union(u, v) and union(u + n, v + n) opposite(u, v): union(u, v + n) and union(u + n, v)

and both kinds of contradiction become plain lookups:

same(u, v) is false when u is already in the same group as v + n opposite(u, v) is false when u is already in the same group as v

Nothing carries a value; the relation is encoded in WHICH element you merge with.

## Why the doubled elements say what they are supposed to

The claim is that after processing a set of consistent claims, u and v share a group exactly when the claims force them onto the same side, and u and v + n share a group exactly when the claims force them onto opposite sides.

Both merges of a claim are made together, which keeps the structure symmetric: whenever a and b are joined, so are a + n and b + n. Then a chain from u to v in the structure alternates between the two halves exactly as often as the chain of claims flips the side, so landing on v means an even number of flips and landing on v + n an odd number. That is the same parity argument as problem 1022, carried by the element numbering instead of by a bit.

## Both merges, every time

Doing only union(u, v + n) for an opposite claim and forgetting union(u + n, v) breaks the symmetry, and the structure then answers some later question with "not related" when it should know the answer. It fails on inputs where the missing half is what a later chain needs, which is what the fifth and seventh tests are for.

## The two claims about one player

same(u, u) is always true and merges nothing new. opposite(u, u) is always false, and the lookup says so: u is trivially in the same group as u.

## Which method to reach for

Problem 1022 solves the same two-sided question by carrying one bit against the parent. That is leaner: n elements instead of 2n, and no chance of forgetting half a merge. The doubling earns its place because it GENERALISES: with three states in a cycle the bit becomes a value modulo 3 and the doubling becomes a tripling, and the tripling needs no modular arithmetic at all. Problem 1024 is that case.

## Overflow

The structure has 2n elements, which is 2 * 10^5, and the answer is at most m. Nothing approaches the 2147483647 a signed 32 bit integer holds.

## Cross-reference

Problem 1022 carries a bit instead of doubling. Problem 988 has only the "same" kind of claim plus a check afterwards, which lets it sort the claims rather than process them in order.

## Cost

Time O((n + m) alpha(n)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ m ≤ 200000` - `t` is 1 or 2. - `1 ≤ u, v ≤ n` - `u` may equal `v`.