broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops):
    parent = {}
    log = []
    MISSING = '<missing>'
    def is_anc(a, x):
        for _ in range(len(parent) + 2):
            if x is None:
                return False
            if x == a:
                return True
            x = parent.get(x)
        return True
    def do(ts, node, par):
        old = parent.get(node, MISSING)
        if not is_anc(node, par):
            parent[node] = par
        log.append([ts, node, par, old])
    def undo(entry):
        if entry[3] == MISSING:
            parent.pop(entry[1], None)
        else:
            parent[entry[1]] = entry[3]
    for op in ops:
        ts = tuple(op[0])
        redo = []
        while log and log[-1][0] > ts:
            entry = log.pop()
            undo(entry)
            redo.append(entry)
        do(ts, op[1], op[2])
        for entry in reversed(redo):
            do(entry[0], entry[1], entry[2])
    return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops):
    parent = {}
    log = []
    MISSING = '<missing>'
    def is_anc(a, x):
        for _ in range(len(parent) + 2):
            if x is None:
                return False
            if x == a:
                return True
            x = parent.get(x)
        return True
    def do(ts, node, par):
        old = parent.get(node, MISSING)
        if (par == 'root' or par in parent or any(e[1] == par for e in log)) and not is_anc(node, par):
            parent[node] = par
        log.append([ts, node, par, old])
    def undo(entry):
        if entry[3] == MISSING:
            parent.pop(entry[1], None)
        else:
            parent[entry[1]] = entry[3]
    for op in ops:
        ts = tuple(op[0])
        redo = []
        while log and log[-1][0] > ts:
            entry = log.pop()
            undo(entry)
            redo.append(entry)
        do(ts, op[1], op[2])
        for entry in reversed(redo):
            do(entry[0], entry[1], entry[2])
    return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Subtrees hang from parents that are not attached anywhere.

Moves [[counter, replica], node, parent] arrive in any order. The replica keeps a log sorted by timestamp. On arrival it undoes every logged move with a larger timestamp (restoring the old parent, or detaching a node that had none), applies the new move, then redoes the undone moves in timestamp order. A move is skipped (logged, tree unchanged) when the parent is neither "root" nor attached, or when the node is the parent or one of its ancestors. Return sorted [node, parent] pairs.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops):
    parent = {}
    log = []
    MISSING = '<missing>'
    def is_anc(a, x):
        for _ in range(len(parent) + 2):
            if x is None:
                return False
            if x == a:
                return True
            x = parent.get(x)
        return True
    def do(ts, node, par):
        old = parent.get(node, MISSING)
        if (par == 'root' or par in parent) and not is_anc(node, par):
            parent[node] = par
        log.append([ts, node, par, old])
    def undo(entry):
        if entry[3] == MISSING:
            parent.pop(entry[1], None)
        else:
            parent[entry[1]] = entry[3]
    for op in ops:
        ts = tuple(op[0])
        redo = []
        while log and log[-1][0] > ts:
            entry = log.pop()
            undo(entry)
            redo.append(entry)
        do(ts, op[1], op[2])
        for entry in redo:
            do(entry[0], entry[1], entry[2])
    return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops):
    parent = {}
    log = []
    MISSING = '<missing>'
    def is_anc(a, x):
        for _ in range(len(parent) + 2):
            if x is None:
                return False
            if x == a:
                return True
            x = parent.get(x)
        return True
    def do(ts, node, par):
        old = parent.get(node, MISSING)
        if (par == 'root' or par in parent) and not is_anc(node, par):
            parent[node] = par
        log.append([ts, node, par, old])
    def undo(entry):
        if entry[3] == MISSING:
            parent.pop(entry[1], None)
        else:
            parent[entry[1]] = entry[3]
    for op in ops:
        ts = tuple(op[0])
        redo = []
        while log and log[-1][0] > ts:
            entry = log.pop()
            undo(entry)
            redo.append(entry)
        do(ts, op[1], op[2])
        for entry in sorted(redo, key=lambda e: e[1]):
            do(entry[0], entry[1], entry[2])
    return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
After a late move, redone moves apply in reverse timestamp order and a stale move wins.

Moves [[counter, replica], node, parent] arrive in any order. The replica keeps a log sorted by timestamp. On arrival it undoes every logged move with a larger timestamp (restoring the old parent, or detaching a node that had none), applies the new move, then redoes the undone moves in timestamp order. A move is skipped (logged, tree unchanged) when the parent is neither "root" nor attached, or when the node is the parent or one of its ancestors. Return sorted [node, parent] pairs.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops):
    parent = {}
    log = []
    MISSING = '<missing>'
    def is_anc(a, x):
        for _ in range(len(parent) + 2):
            if x is None:
                return False
            if x == a:
                return True
            x = parent.get(x)
        return True
    def do(ts, node, par):
        old = parent.get(node, MISSING)
        if (par == 'root' or par in parent) and not is_anc(node, par):
            parent[node] = par
        log.append([ts, node, par, old])
    def undo(entry):
        if entry[3] == MISSING:
            parent[entry[1]] = None
        else:
            parent[entry[1]] = entry[3]
    for op in ops:
        ts = tuple(op[0])
        redo = []
        while log and log[-1][0] > ts:
            entry = log.pop()
            undo(entry)
            redo.append(entry)
        do(ts, op[1], op[2])
        for entry in reversed(redo):
            do(entry[0], entry[1], entry[2])
    return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops):
    parent = {}
    log = []
    MISSING = '<missing>'
    def is_anc(a, x):
        for _ in range(len(parent) + 2):
            if x is None:
                return False
            if x == a:
                return True
            x = parent.get(x)
        return True
    def do(ts, node, par):
        old = parent.get(node, MISSING)
        if (par == 'root' or par in parent) and not is_anc(node, par):
            parent[node] = par
        log.append([ts, node, par, old])
    def undo(entry):
        if entry[3] == MISSING:
            parent[entry[1]] = 'root'
        else:
            parent[entry[1]] = entry[3]
    for op in ops:
        ts = tuple(op[0])
        redo = []
        while log and log[-1][0] > ts:
            entry = log.pop()
            undo(entry)
            redo.append(entry)
        do(ts, op[1], op[2])
        for entry in reversed(redo):
            do(entry[0], entry[1], entry[2])
    return sorted([k, v] for k, v in parent.items())
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[4, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[3, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[6, 'a'], 'm', 'k'], [[5, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[6, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[6, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[3, 'a'], 'q', 'root'], [[5, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[5, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[4, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[5, 'b'], 'p', 'q'], [[4, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[6, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[3, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    2: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[5, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[4, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[7, 'a'], 'm', 'k'], [[6, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[7, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[7, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[4, 'a'], 'q', 'root'], [[6, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[6, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[5, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[6, 'b'], 'p', 'q'], [[5, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[7, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[4, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    3: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[6, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[5, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[8, 'a'], 'm', 'k'], [[7, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[8, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[8, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[5, 'a'], 'q', 'root'], [[7, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[7, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[6, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[7, 'b'], 'p', 'q'], [[6, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[8, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[5, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    4: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[7, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[6, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[9, 'a'], 'm', 'k'], [[8, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[9, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[9, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[6, 'a'], 'q', 'root'], [[8, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[8, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[7, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[8, 'b'], 'p', 'q'], [[7, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[9, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[6, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
    5: [('moves arriving in order', [[[[1, 'a'], 'x', 'root'], [[2, 'a'], 'y', 'x'], [[3, 'a'], 'z', 'y']]], [['x', 'root'], ['y', 'x'], ['z', 'y']]), ('late earlier move is replayed underneath', [[[[1, 'a'], 'x', 'root'], [[3, 'a'], 'x', 'y'], [[2, 'b'], 'y', 'root']]], [['x', 'y'], ['y', 'root']]), ('concurrent moves that would form a cycle', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'a'], 'p', 'q'], [[3, 'b'], 'q', 'p']]], [['p', 'q'], ['q', 'root']]), ('same cycle in the other arrival order', [[[[1, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'root'], [[3, 'b'], 'q', 'p'], [[3, 'a'], 'p', 'q']]], [['p', 'q'], ['q', 'root']]), ('moving a node under its grandchild is skipped', [[[[1, 'a'], 'g', 'root'], [[2, 'a'], 'h', 'g'], [[3, 'a'], 'i', 'h'], [[8, 'a'], 'g', 'i']]], [['g', 'root'], ['h', 'g'], ['i', 'h']]), ('move to a parent that does not exist yet', [[[[1, 'a'], 'c', 'ghost'], [[2, 'a'], 'ghost', 'root'], [[7, 'a'], 'c', 'ghost']]], [['c', 'ghost'], ['ghost', 'root']]), ('moving under the current grandparent is allowed', [[[[1, 'a'], 'u', 'root'], [[2, 'a'], 'v', 'u'], [[3, 'a'], 'w', 'v'], [[4, 'a'], 'w', 'u'], [[5, 'a'], 'w', 'root']]], [['u', 'root'], ['v', 'u'], ['w', 'root']]), ('several late moves replay in timestamp order', [[[[1, 'a'], 'm', 'root'], [[10, 'a'], 'm', 'k'], [[9, 'a'], 'm', 'j'], [[2, 'b'], 'k', 'root'], [[3, 'b'], 'j', 'root']]], [['j', 'root'], ['k', 'root'], ['m', 'k']]), ('late creation undone and redone', [[[[2, 'a'], 'r', 'root'], [[1, 'b'], 'r', 'root'], [[3, 'a'], 's', 'r']]], [['r', 'root'], ['s', 'r']]), ('move under an unattached parent is skipped', [[[[10, 'a'], 'r', 'q'], [[1, 'b'], 'p', 'p']]], []), ('parent whose own move was skipped is not attached', [[[[3, 'b'], 'p', 'r'], [[10, 'b'], 'r', 'p']]], []), ('late move replays newer moves in timestamp order', [[[[7, 'a'], 'q', 'root'], [[9, 'a'], 'p', 'q'], [[1, 'a'], 'r', 'q']]], [['p', 'q'], ['q', 'root']]), ('late move before a child creation', [[[[9, 'a'], 'p', 'root'], [[2, 'a'], 'q', 'p'], [[1, 'a'], 'q', 'r']]], [['p', 'root']]), ('undoing a skipped first move leaves no entry', [[[[8, 'b'], 'p', 'r'], [[1, 'b'], 'p', 'p']]], []), ('undoing a skipped first move does not attach', [[[[9, 'b'], 'p', 'q'], [[8, 'a'], 'r', 'r']]], []), ('two newer moves undone for one late move', [[[[3, 'b'], 'q', 'r'], [[10, 'b'], 'p', 'q'], [[1, 'b'], 'r', 'root']]], [['p', 'q'], ['q', 'r'], ['r', 'root']]), ('skipped move leaves the node in place', [[[[2, 'b'], 'r', 'p'], [[2, 'a'], 'p', 'root'], [[7, 'b'], 'r', 'q']]], [['p', 'root'], ['r', 'p']])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A node that has not been created yet appears in the tree with a null parent.

Moves [[counter, replica], node, parent] arrive in any order. The replica keeps a log sorted by timestamp. On arrival it undoes every logged move with a larger timestamp (restoring the old parent, or detaching a node that had none), applies the new move, then redoes the undone moves in timestamp order. A move is skipped (logged, tree unchanged) when the parent is neither "root" nor attached, or when the node is the parent or one of its ancestors. Return sorted [node, parent] pairs.

split: open-access


prompt:
Removed elements keep appearing as members.

Each replica maps elements to a causal length. An element is present when its length is odd. ["add", r, e] increments the length only when it is even; ["rem", r, e] increments it only when it is odd. ["merge", s, d] takes the per-element maximum. Return per replica the sorted members and the sorted [element, length] pairs.

split: open-access


prompt:
A duplicate add removes the element.

Each replica maps elements to a causal length. An element is present when its length is odd. ["add", r, e] increments the length only when it is even; ["rem", r, e] increments it only when it is odd. ["merge", s, d] takes the per-element maximum. Return per replica the sorted members and the sorted [element, length] pairs.

split: open-access


prompt:
A remove of something not in the set makes it appear.

Each replica maps elements to a causal length. An element is present when its length is odd. ["add", r, e] increments the length only when it is even; ["rem", r, e] increments it only when it is odd. ["merge", s, d] takes the per-element maximum. Return per replica the sorted members and the sorted [element, length] pairs.

split: open-access


prompt:
A stale present copy revives an element that was later removed.

Each replica maps elements to a causal length. An element is present when its length is odd. ["add", r, e] increments the length only when it is even; ["rem", r, e] increments it only when it is odd. ["merge", s, d] takes the per-element maximum. Return per replica the sorted members and the sorted [element, length] pairs.

split: open-access