Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
ABC = []
for _ in range(N-1):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x,y = map(int, input().split())
    XY.append((x,y))
    
# bellman_ford(edges,num_v,source)
# エッジのリストと超点数、スタート地点をinput
# リターンはスタート地点からの各ノードへの最短距離、負の閉路があれば-1*INT_MAXを返す


import sys
INT_MAX = sys.maxsize # 9223372036854775807

def bellman_ford(edges,num_v,source):

    dist=[INT_MAX] * num_v
    dist[source]=0

    #辺の緩和
    has_negative = False
    for i in range(num_v):
        for edge in edges:
            if edge[0] != INT_MAX and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1:
                    has_negative = True
    
    if has_negative == False:
        return dist
    
    negative = [False] * num_v
    for i in range(num_v):
        for from_edge, to_edge, cost in edges:
            if dist[from_edge] == INT_MAX:
                continue
            if dist[to_edge] > dist[from_edge] + cost:
                dist[to_edge] = dist[from_edge] + cost
                negative[to_edge] = True
            
            if negative[from_edge] == INT_MAX:
                negative[to_edge] = True
                
    for i, is_negative in enumerate(negative):
        if is_negative:
            dist[i] = -1 * INT_MAX
        
    return dist



edges = ABC[:]
for a,b,c in edges[:]:
    edges.append((b,a,c))


shortest = bellman_ford(edges, N+1, K)
    
question = XY[:]

for x,y in question:
    ans = shortest[x] + shortest[y]
    print(ans)


### FIXED CODE ###

N = int(input())
ABC = []
for _ in range(N-1):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))

Q, K = map(int, input().split())
XY = []
for _ in range(Q):
    x,y = map(int, input().split())
    XY.append((x,y))
    
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shortest = dijkstra(graph, K)
#print(shortest)

questions = XY

for x,y in questions:
    ans = shortest[x] + shortest[y]
    print(ans)
### BUGGY CODE ###

import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 is vf2: continue
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)

### FIXED CODE ###

import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 is vf2: continue
        if len(vf1) < len(vf2): vf1, vf2 = vf2, vf1
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    ans += L//a
  print(ans%MOD)

if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

if __name__ == '__main__':
  main()
### BUGGY CODE ###

S = input()
n = len(S)
count = 0
T = [0] * (n + 1)
mod = 0
x = 1
mod_dict = {i:0 for i in range(2019)}
mod_dict[0] = 1
for s in reversed(S):
    mod = (mod + (int(s) * x)) % 2019
    mod_dict[mod] = mod_dict[mod] + 1
    x = x * 10

count = 0
for k, v in mod_dict.items():
    count = count + v*(v-1)//2

print(count)


### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

print(count)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for i in range(Q):
  l,r=map(int,input().split())
  A=S[l-1:r]
  print(A.count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
A=[0]
res=0
for i in range(N):
  if i !=0:
    if S[i-1]=="A" and S[i]=="C":
      res+=1
      A.append(res)
    else:
      A.append(res)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
### BUGGY CODE ###

N , K = map(int, input().split())
A = list(map(int, input().split()))

x = 1
for a in A[:K]:
    x *= a
for i in range(K, N):
    xx = x // A[i-K] * A[i]
    if xx > x:
        print('Yes')
    else:
        print('No')
    x = xx

### FIXED CODE ###

N , K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(K, N):
    x = A[i] / A[i-K]
    if x > 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
cnt = 0
cur = 0
while cur<N:
    x = X[cur][0]
    if X[cur][1]%A==0:
        n = X[cur][1]//A
    else:
        n = X[cur][1]//A+1
    ind = bisect_right(X,[x+2*D,10**10])
    for i in range(cur,ind):
        X[i][1] -= n*A
    cnt += n
    flag = 0
    for i in range(cur+1,N):
        if X[i][1]>0:
            cur = i
            flag = 1
            break
    if flag==0:cur=N
print(cnt)    

### FIXED CODE ###

from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,N):
        delta += B[i]
        B[i] = 0
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)
### BUGGY CODE ###

n,a,b = map(int,input().split())

turn = 1
while abs(a-b) != 1:  
  if turn == 1:
    if a<b:
      if (b-a)%2==0 or a==1: a += 1
      else: a -=1
    else:
      if (a-b)%2==0 or a==n: a -= 1
      else: a +=1
  else:
    if a<b:
      if (b-a)%2==1 or b==1: b += 1
      else: b -=1
    else:
      if (a-b)%2==1 or b==n: b -= 1
      else: b +=1
  turn *= -1
print('Alice' if turn==-1 else 'Borys')

### FIXED CODE ###

n,a,b = map(int,input().split())
print('Alice' if abs(b-a)%2==0 else 'Borys')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
m = 10**9 + 7
for i in range(len(a)):
    for j in range(i+1, len(a)): 
        ans += a[i] * a[j]
print(ans % m)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 10 ** 9 + 7
ans = 0
s = 0
for i in range(n-1, -1, -1):
    ans += s * a[i]
    s += a[i]
print(ans % c)
### BUGGY CODE ###

N,M=map(int,input().split())
now=0
MOD=10**9+7
p=[1,0]#0 humu  1 humazu
A=[int(input()) for i in range(M)]+[-1]
while now<N:
  if now==A[0]-1:
    p=[0,p[0]]
    A=A[1:]
  else:
    p=[p[0]+p[1], p[0]]
  now+=1
print(p[0]%MOD)

### FIXED CODE ###

N,M=map(int,input().split())
now=0
a=0
MOD=10**9+7
p=[1,0]#0 humu  1 humazu
A=[int(input()) for i in range(M)]+[-1]
while now<N:
  if now==A[a]-1:
    p=[0,p[0]]
    a+=1
  else:
    p=[(p[0]+p[1])%MOD, p[0]%MOD]
  now+=1
print(p[0]%MOD)
### BUGGY CODE ###

INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append([a - 1, b - 1,  -c])

for j in range(N):
    for i in range(M):
        if d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]

for i in range(N):
    for j in range(M):
        if d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True

        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

if loop[N - 1]:
    print('inf')
else:
    print(ans)

### FIXED CODE ###

INF = 10 ** 18
N, M = map(int, input().split())
abc = []
d = [INF] * N
d[0] = 0
loop = [False] * N

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append([a - 1, b - 1,  -c])

for j in range(N):
    for i in range(M):
        if d[abc[i][1]] > d[abc[i][0]] + abc[i][2]:
            d[abc[i][1]] = d[abc[i][0]] + abc[i][2]
ans = -1 * d[-1]

for i in range(N):
    for j in range(M):
        if d[abc[j][1]] > d[abc[j][0]] + abc[j][2]:
            d[abc[j][1]] = d[abc[j][0]] + abc[j][2]
            loop[abc[j][1]] = True

        if loop[abc[j][0]] == True:
            loop[abc[j][1]] = True

if loop[N - 1]:
    print('inf')
else:
    print(ans)
### BUGGY CODE ###

def main(): 
  def modinv(a, mod=10**9+7):
      return pow(a, mod-2, mod)

  def comb(n, r, mod=10**9+7):
      r = min(r, n-r)
      res = 1
      for i in range(r):
          res = res * (n - i) * modinv(i+1, mod) % mod
      return res

  import sys
  input = sys.stdin.readline
  mod = 10**9+7  
  n,k = [int(i) for i in input().split()]
  a = [int(i) for i in input().split()]
  a = sorted(a)
  a = tuple(a)

  ans = 0
  for i in range(0,n-k+1):
    p = a[i]*comb(n-1-i,k-1,mod)
    ans -= (p%mod)
    ans %= mod
  for i in range(k-1,n):
    q = a[i]*comb(i,k-1,mod)
    ans += (q%mod)
    ans %= mod
  print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        # モジュラ逆数の性質
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

import sys
input = sys.stdin.readline
mod = 10**9+7  
n,k = [int(i) for i in input().split()]
fact, fact_inv = make_array_for_comb(n,mod)
a = [int(i) for i in input().split()]
a = sorted(a)
a = tuple(a)

ans = 0
for i in range(0,n-k+1):
  p = a[i]*comb(n-1-i,k-1,mod)
  ans -= (p%mod)
  ans %= mod
for i in range(k-1,n):
  q = a[i]*comb(i,k-1,mod)
  ans += (q%mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
ps = list(map(int, input().split()))
ans = 0
max_ps = 0
start = 0

for i in range(n):
    if max_ps <= sum(ps[i:i+k]):
        start = i
        max_ps = sum(ps[i:i+k])

for i in ps[start:start+k]:
    ans+=sum(range(i+1))/i

print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
ps = list(map(int, input().split()))

tmp = sum(ps[:k])
max_ps = tmp
start = 0

for i in range(1,n-k+1):
    tmp = tmp-ps[i-1]+ps[i+k-1]
    if tmp >= max_ps:
        max_ps = tmp
        start = i

print(sum([(i*(i+1))/ (2*i) for i in ps[start:start+k]]))
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()

cnt = 0
for i in range(0, n):
    for j in range(i, n):
        if int(s[i:j+1]) % p == 0:
            cnt += 1

print(cnt)


### FIXED CODE ###

N,P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = [0]*P
    mod_cnt[0] = 1
    k = 0.1
    t = 0
    for i in range(1, N+1):
        k = int(k * 10) % P
        t = (t + k * int(S[-i])) % P
        mod_cnt[t] += 1
    ans = 0
    for cnt in mod_cnt:
        ans += (cnt * (cnt-1)) // 2
    print(ans)
### BUGGY CODE ###

import math
q = int(input())
list_range = [list(map(int, input().split())) for _ in range(q)]

max_range = math.sqrt(10**5)
list_search = [i for i in range(2, 10**5 + 1)]
list_prime = []
while list_search[0] <= max_range:
  list_prime.append(list_search[0])
  temp = list_search[0]
  list_search = [i for i in list_search if i % temp != 0]
list_prime.extend(list_search)

list_satisfy = []
for one_prime in list_prime:
  if one_prime * 2 > 10**5:
    break
  if one_prime * 2 - 1 in list_prime:
    list_satisfy.append(one_prime * 2 - 1)

for l, r in list_range:
  result = len([i for i in list_satisfy if l <= i <= r])
  print(result)

### FIXED CODE ###

q = int(input())
list_range = [list(map(int, input().split())) for _ in range(q)]

list_flag_prime = [1 for i in range(10**5+1)]
list_flag_prime[0:2] = [0, 0]
for i in range(2, 10**5+1):
  if list_flag_prime[i] == 1:
    for j in range(2*i, 10**5+1, i):
      list_flag_prime[j] = 0

list_subj = [0 for i in range(10**5+1)]
for i in range(3, 10**5+1, 2):
  if list_flag_prime[i] == 1 & list_flag_prime[int((i+1)/2)] == 1:
    list_subj[i] += 1

list_satisfy = [0 for i in range(10**5+1)]
for i in range(1, 10**5+1):
  list_satisfy[i] += list_satisfy[i-1] + list_subj[i]

for l, r in list_range:
  print(list_satisfy[r] - list_satisfy[l-1])
### BUGGY CODE ###

def main():
  n,q=map(int,input().split())
  a=[[i] for i in range(n+1)]
  b=[0 for i in range(n+1)]
  
  for i in range(n-1):
    x,y=map(int,input().split())
    for j in range(n-1):
      if x in a[j]:
        a[j].append(y)
#        print(a)
 
#  print("aaa",a)
  for i in range(q):
    x,y=map(int,input().split())
#    print("c,y",x,y)
#    print("ax",a[x])
#    print("B",b)
    for j in a[x]:
#      print("j",j)
      b[j-1]+=y
#      print(b)

       
  print(*b[:n])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  n,q=map(int,input().split())
  a=[0]*(n-1)
  c=[0 for i in range(n)]
  for i in range(n-1):
    a[i]=list(map(int,input().split()))

  a.sort()

  for i in range(q):
    x,y=map(int,input().split())
    c[x-1]+=y
  for i in range(n-1):
    c[a[i][1]-1]+=c[a[i][0]-1]
  print(*c)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
total=sum(a)
ans=[]
for i in range(1,n):
    x=sum(a[0:i])
    ans.append(abs(2*x-total))
print(min(ans))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
v=sum(a)
x=sum(a)
ans=[]
for i in range(n-1):
    x=x-a[i]
    ans.append(abs(v-2*x))
print(min(ans))
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()
ans = 0

#for i in range(n):
l = 0
while True:
    if l == n - 2:
        break
    m = l
    r = l + 1
    cnt = 0

    if s[l] == '0':
        cnt += 1

    while True:
        #print(l, r)
        if r > n - 1:
            break

        if s[r] == '0':
            if s[r-1] == '1':
                cnt += 1
                if cnt > k:
                    break
        else:
            if s[r-1] == '0' and cnt == 1:
                m = r
        r += 1
    ans = max(ans, r - l)
    #print('[C] ans:', ans)
    l = m


print(ans)

'''
5 1
00010

14 2
11101010110011
'''


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
r = 1
ans = 0
cnt = 0

for l in range(0, n):
    if l == 0:
        if s[l] == '0':
            cnt += 1

    if l > 0 and s[l] == '1' and s[l-1] == '0':
        cnt -= 1

    while True:
        # print('\n', l, r)
        # print('count:', cnt)
        if r > n - 1:
            length = r - l
            ans = max(ans, length)
            break

        if s[r] == '0' and s[r-1] == '1':
            if cnt < k:
                cnt += 1
            else:
                # print('over!')
                length = r - l
                ans = max(ans, length)
                break
        r += 1

print(ans)
### BUGGY CODE ###

import copy
from collections import deque


H, W = map(int, input().split())
past_map = [list(input()) for _ in range(H)]


def make_new_map(p_map):

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    update_flag = False
    n_map = copy.deepcopy(p_map)
    reached = [[False for _ in range(W)] for _ in range(H)]

    for sh in range(H):
        for sw in range(W):
            if (reached[sh][sw] is False) and (p_map[sh][sw] == '#'):
                # start bfs
                togo = deque()
                togo.append((sh, sw))
                reached[sh][sw] = True
                while len(togo):
                    h, w = togo[0][0], togo[0][1]
                    togo.popleft()
                    for d in range(4):
                        nh, nw = h + dy[d], w + dx[d]
                        if nh < 0 or nw < 0 or nh >= H or nw >= W:
                            continue
                        if reached[nh][nw] is True:
                            continue
                        if n_map[nh][nw] == '.':
                            n_map[nh][nw] = '#'
                            update_flag = True
                        if p_map[nh][nw] == '.':
                            continue
                        togo.append((nh, nw))
                        reached[nh][nw] = True
    return n_map, update_flag


count = 0
past_map, flag = make_new_map(past_map)
while flag:
    count += 1
    past_map, flag = make_new_map(past_map)
print(count)


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

checked = [[False for _ in range(W)] for _ in range(H)]

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            checked[i][j] = True
        else:
            flag = True

if flag is False:
    print('0')
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1
### BUGGY CODE ###

N = int(input())
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x.copy())
    B.append(x.copy())

for k in range(N):
    for i in range(N):
        for j in range(N):
            B[i][j] = min(B[i][j],B[i][k]+ B[k][j])

if A!=B:
    print(-1)
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)



### FIXED CODE ###

N = int(input())
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x[:])
    B.append(x[:])

for k in range(N):
    for i in range(N):
        for j in range(N):
            B[i][j] = min(B[i][j],B[i][k]+ B[k][j])

if A!=B:
    print(-1)
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)
### BUGGY CODE ###

import sys
import math
N = int(input())
A = list(map(int, input().split()))

s = 0
for i in range(N):
    for j in range(i+1,N):
        s += A[i] * A[j]
        if s > 10 ** 9 + 7:
            s = s % (10 ** 9 + 7)
print(s)


### FIXED CODE ###

import sys
import math
N = int(input())
A = list(map(int, input().split()))

s = 0
d = 0
for j in range(1,N):
    d += A[j]

for i in range(N-1):
    s += d * A[i]
    if s > 10 ** 9 + 7:
        s = s % (10 ** 9 + 7)
    d -= A[i+1]

print(s)
### BUGGY CODE ###

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = q
    prevQ = get_unique_list(prevQ)
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
    for i,j in prevQ:
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)

### FIXED CODE ###

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = list(map(list, set(map(tuple, q))))
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print(-1)
        exit()
print(day)