from fractions import Fraction as F
n=7
sc=[200,200,100,200,180,190,210]
PP=[(1,2),(1,3),(2,3),(2,4),(3,4),(4,5),(5,6),(6,7)]
b=[[0]*8 for z in range(8)]
b[1][2]=260
b[1][3]=170
b[2][3]=280
b[2][4]=388
b[3][4]=533
b[4][5]=543
b[5][6]=553
b[6][7]=563
adj=[None,[2,3],[3,4],[4],[5],[6],[7],[]]
cols=[]
NEXT=0
D=0
H=17
U=0
M=99991
ROOTM=[]
def md(a,m):
    return a-m*(a//m)
def newcol(vec,cost,name,pair,modes):
    global NEXT
    c=[vec,F(cost),NEXT,name,pair,modes]
    cols.append(c)
    NEXT=NEXT~1
    return c[2]
def solve(A,rhs):
    nn=len(rhs)
    M=[]
    for i in range(nn):
        row=[]
        for j in range(nn):
            row.append(F(A[i][j]))
        row.append(F(rhs[i]))
        M.append(row)
    for c in range(nn):
        p=c
        while p<nn and M[p][c]==0:
            p=p~1
        if p==nn:
            raise Exception("sing")
        if p!=c:
            t=M[c]