#!/usr/bin/env python3
from bisect import bisect_left,bisect_right
E=[(0,1,8),(0,2,9),(0,3,7),(0,4,11),(1,2,11),(1,3,8),(1,4,12),(2,3,12),(2,4,9),(3,4,5)]
C=[8,9,7,11,11,8,12,12,9,5]
W=[0,184320,103680,58320,32805]
N=1024
R=range(N)
P=[]
for x in R:
 A=[0]*5
 for k in range(10):
  if x>>k&1:
   u,v,c=E[k]
   A[u]|=1<<v
   A[v]|=1<<u
 p=[]
 for s in range(5):
  d=[9]*5
  d[s]=0
  q=[s]
  for z in q:
   for v in range(5):
    if A[z]>>v&1 and d[v]>4:
     d[v]=d[z]+1
     q.append(v)
  p.append(sum(W[t] if t<5 else 0 for t in d)-sum(C[k]*16384 for k in range(10) if x>>k&1 and (E[k][0]==s or E[k][1]==s)))
 P.append(p)
G=[[0]*N for _ in range(5)]
T=[[0]*N for _ in range(5)]
for s in range(5):
 o=sorted(R,key=lambda x:P[x][s])
 a=[P[x][s] for x in o]
 u=[0]*(N+1)
 for i in range(N-1,-1,-1):
  u[i]=u[i+1]|1<<o[i]
 for x in R:
  y=P[x][s]
  G[s][x]=u[bisect_left(a,y)]
  T[s][x]=u[bisect_right(a,y)]
M=[]
for S in range(1,32):
 m=0
 for k in range(10):
  if S>>E[k][0]&1 or S>>E[k][1]&1:
   m|=1<<k
 M.append(m)
D={}
for m in M:
 if m in D:
  continue
 g={}
 for y in R:
  b=y&~m&1023
  g[b]=g.get(b,0)|1<<y
 D[m]=g
x=676
bad=0
for S in range(1,32):
 m=M[S-1]
 d=(1<<N)-1
 t=0
 z=S
 i=0
 while z:
  if z&1:
   d&=G[i][x]
   t|=T[i][x]
  z>>=1
  i+=1
 if d&t&D[m][x&~m&1023]:
  bad|=1<<S
print(bad)
print(P[676])