"""Part 4: colour the floor like a chessboard, or prove that it can't be done.

Part 3's lower bound on the fewest commands leans on the checkerboard: every step lands on the
other colour. On a flat floor that colouring is (row + column) mod 2 and needs no checking. A
room that wraps round an odd number of fields, or the corner of a box, can break it, so here the
colouring is built by breadth-first search instead, and a failure comes with its evidence.

Breadth-first search colours each field by the parity of its distance from the start. If two
neighbours end up with the same colour, their distances have the same parity, and their two tree
paths back to where they meet, plus the step between them, form a loop of odd length. A graph
with an odd loop can't be coloured with two colours (the colours would have to alternate all the
way round and come back wrong), so the loop is a certificate: anyone can check it without
trusting the search.
"""
from collections import deque


def neighbours(surface, f):
    return [g for g, _, _ in (x for x in surface.glue[f] if x is not None)]


def two_colour(surface, start):
    """('colours', {field: 0 or 1}) for a proper colouring of the floor reachable from start,
    or ('odd loop', [fields in order round a loop of odd length])."""
    depth = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        f = queue.popleft()
        for g in neighbours(surface, f):
            if g not in depth:
                depth[g] = depth[f] + 1
                parent[g] = f
                queue.append(g)
            elif depth[g] % 2 == depth[f] % 2:
                return 'odd loop', odd_loop(parent, depth, f, g)
    return 'colours', {f: d % 2 for f, d in depth.items()}


def odd_loop(parent, depth, a, b):
    """Walk a and b up their tree paths until they meet. The loop is a's path up to the meeting
    field, back down b's path, and the step from b to a."""
    left, right = [a], [b]
    while a != b:
        if depth[a] >= depth[b]:
            a = parent[a]
            left.append(a)
        else:
            b = parent[b]
            right.append(b)
    return left + right[-2::-1]         # the meeting field once, then down to b


def is_odd_loop(surface, loop):
    """Check a certificate: consecutive fields (and last and first) are neighbours, no field
    repeats, and the length is odd."""
    if len(loop) % 2 == 0 or len(set(loop)) != len(loop):
        return False
    return all(loop[(i + 1) % len(loop)] in neighbours(surface, loop[i]) for i in range(len(loop)))