"""Part 5: union-find that also remembers which way round each field is.

Plain union-find keeps groups of connected fields: every field points at a parent, the root of
its tree names the group, and two fields are connected exactly when their roots are the same.
Here every field also stores one bit, its parity: whether it is mirrored relative to its parent.
Adding up the bits on the way to the root says whether a field is mirrored relative to its root,
and two fields in one group are mirrored relative to each other when those two answers differ.

Joining two fields says how they are related: `union(a, b, p)` records "b is mirrored relative to
a" when p is 1. If a and b are already in one group, the structure checks the claim against what
it knows instead. A claim that disagrees is a loop with an odd number of mirrorings: a loop that
turns the robot over. The same bit read as "different colour" finds odd loops for Part 4's
checkerboard.

Both usual speed-ups apply. Union by size hangs the smaller tree under the larger, and path
compression points every field it passes straight at the root, adjusting its bit so it still
means the same thing. Together they make each operation take almost constant time on average.
"""


class ParityDSU:
    def __init__(self):
        self.parent = {}
        self.bit = {}                   # mirrored relative to the parent?
        self.size = {}
        self.consistent = True          # no loop has contradicted a claim yet

    def add(self, x):
        if x not in self.parent:
            self.parent[x], self.bit[x], self.size[x] = x, 0, 1

    def find(self, x):
        """(root, parity of x relative to the root), compressing the path on the way back."""
        path = []
        while self.parent[x] != x:
            path.append(x)
            x = self.parent[x]
        root, parity = x, 0
        for y in reversed(path):        # nearest the root first
            parity ^= self.bit[y]
            self.parent[y], self.bit[y] = root, parity
        return root, (self.bit[path[0]] if path else 0)

    def union(self, a, b, p):
        """Record that b's parity relative to a is p. Returns 'joined' if that joined two
        groups, 'agrees' if it was already known, or 'contradicts' for an odd loop."""
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        if ra == rb:
            if pa ^ pb == p:
                return 'agrees'
            self.consistent = False
            return 'contradicts'
        if self.size[ra] < self.size[rb]:
            ra, rb, pa, pb = rb, ra, pb, pa
        self.parent[rb] = ra
        self.bit[rb] = pa ^ pb ^ p      # so that parity(b) = parity(a) ^ p holds through ra
        self.size[ra] += self.size[rb]
        return 'joined'

    def same_frame(self, a, b):
        """None if a and b aren't connected yet, else whether they are the same way round."""
        ra, pa = self.find(a)
        rb, pb = self.find(b)
        return None if ra != rb else pa == pb