"""A delivery manifest assembled by relinking existing singly linked nodes."""
from dataclasses import dataclass


@dataclass(eq=False)
class Node:
    value: int
    next: "Node | None" = None


def from_values(values):
    dummy = tail = Node(0)
    for value in values:
        tail.next = Node(value)
        tail = tail.next
    return dummy.next


def assert_acyclic(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            raise ValueError("cyclic manifest")


def to_values(head):
    assert_acyclic(head)
    values = []
    while head is not None:
        values.append(head.value)
        head = head.next
    return values


def _sorted_tail(head):
    tail = None
    while head is not None:
        if not isinstance(head.value, int):
            raise ValueError("manifest values must be integers")
        if head.next is not None and head.value > head.next.value:
            raise ValueError("input manifests must be sorted")
        tail, head = head, head.next
    return tail


def merge_sorted(left, right):
    dummy = tail = Node(0)
    while left is not None and right is not None:
        if left.value <= right.value:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left if left is not None else right
    return dummy.next


def remove_cancelled(head, cancelled):
    dummy = Node(0, head)
    previous = dummy
    while previous.next is not None:
        if previous.next.value in cancelled:
            previous.next = previous.next.next
        else:
            previous = previous.next
    return dummy.next


def reverse_complete_groups(head, size):
    if size < 1:
        raise ValueError("group size must be positive")
    dummy = Node(0, head)
    before = dummy
    while True:
        last = before
        for _ in range(size):
            last = last.next
            if last is None:
                return dummy.next
        after, first = last.next, before.next
        previous, current = after, first
        while current is not after:
            following = current.next
            current.next = previous
            previous, current = current, following
        before.next = last
        before = first


def build_manifest(left, right, cancelled=(), group_size=2):
    """Consume two sorted disjoint acyclic lists; cancel IDs, then reverse full crates."""
    if not isinstance(group_size, int) or group_size < 1:
        raise ValueError("group_size must be a positive integer")
    assert_acyclic(left); assert_acyclic(right)
    left_tail, right_tail = _sorted_tail(left), _sorted_tail(right)
    if left_tail is not None and left_tail is right_tail:
        raise ValueError("input manifests share nodes")
    cancelled = set(cancelled)
    return reverse_complete_groups(remove_cancelled(merge_sorted(left, right), cancelled), group_size)