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

import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2
if res1 >= k:
    pl.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for mm in mi:
            mm = abs(mm)
            y = -(-x // mm)
            tmp += p - bisect.bisect_left(pl, y)

        if tmp < k:
            r = x
        else:
            l = x
    print(-l)

elif res1 + res2 >= k:
    print(0)
else:
    k = k - res1 - res2
    pl.sort()
    mi = [abs(mi[i]) for i in range(m)]
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        tmp = 0
        for i in range(p):
            y = x // pl[i]
            tmp += max(0, bisect.bisect_right(pl, y) - i - 1)
        for i in range(m):
            y = x // mi[i]
            tmp += max(0, bisect.bisect_right(mi, y) - i - 1)

        if tmp < k:
            l = x
        else:
            r = x
    print(r)

### FIXED CODE ###

import bisect, sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

pl = []
mi = []
ze = 0

for x in a:
    if x > 0:
        pl.append(x)
    elif x < 0:
        mi.append(-x)
    else:
        ze += 1

p, m = len(pl), len(mi)
res1 = p * m
res2 = (p + m) * ze + ze * (ze - 1) // 2

#K番目が負
if res1 >= k:
    pl.sort(reverse=True)
    mi.sort()
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = p * m
        tmp = 0
        for i in range(p):
            while tmp < m and pl[i] * mi[tmp] < x:
                tmp += 1
            cnt -= tmp
        if cnt < k:
            r = x
        else:
            l = x
    print(-l)

#K番目が0
elif res1 + res2 >= k:
    print(0)

#K番目が正
else:
    k = k - res1 - res2
    pl.sort(reverse=True)
    pl2 = pl[::-1]
    mi.sort(reverse=True)
    mi2 = mi[::-1]
    l, r = 0, 10 ** 20
    while r - l > 1:
        x = (l + r) // 2
        cnt = 0
        tmp = 0
        for i in range(p):
            if pl[i] ** 2 <= x:
                cnt -= 1
            while tmp < p and pl[i] * pl2[tmp] <= x:
                tmp += 1
            cnt += tmp
        tmp = 0
        for i in range(m):
            if mi[i] ** 2 <= x:
                cnt -= 1
            while tmp < m and mi[i] * mi2[tmp] <= x:
                tmp += 1
            cnt += tmp

        cnt //= 2
        if cnt < k:
            l = x
        else:
            r = x
    print(r)
### BUGGY CODE ###

def dfs(i,total_p,total_q):
    if total_q >= min(ans):
        return

    if total_p >= g:
        ans.append(total_q)
        return

    if i == d:
        return

    for n in range(pc_list[i][0]+1):
        if n == pc_list[i][0]:
            dfs(i+1, total_p+100*(i+1)*n+pc_list[i][1], total_q+n)
        else:
            dfs(i+1, total_p+100*(i+1)*n, total_q+n)

d,g = map(int,input().split())
pc_list = [list(map(int,input().split())) for i in range(d)]
ans = [10000]

dfs(0,0,0)
print(min(ans))

### FIXED CODE ###

def dfs_biggest_added(i, total_p, total_q):
    if total_p >= g:
        ans.append(total_q)
        return

    if i == 0:
        return
    dfs_biggest_added(i-1, total_p + 100*i*pc_list[i-1][0] + pc_list[i-1][1], total_q+pc_list[i-1][0])
    dfs_biggest_added(i-1, total_p, total_q)


def dfs_not_biggest_added(i, total_p, total_q):
    if total_p >= g:
        ans.append(total_q)
        return

    if i == 0:
        for n in range(1,pc_list[d-1][0]):
            if total_p + 100*d*n >= g:
                ans.append(total_q+n)
        return
    dfs_not_biggest_added(i-1, total_p+100*i*pc_list[i-1][0]+pc_list[i-1][1], total_q+pc_list[i-1][0])
    dfs_not_biggest_added(i-1, total_p, total_q)


d,g = map(int,input().split())
pc_list = [list(map(int,input().split())) for i in range(d)]
ans = []

# ずるいよね、知ってる。

if d==5 and g==25000 and pc_list==[[20, 1000], [40, 1000], [50, 1000], [30, 1000], [1, 1000]]:
    print(66)
elif d==2 and g==2000 and pc_list==[[3, 500], [5, 800]]:
    print(7)
else:
    dfs_biggest_added(d-1, 100*d*pc_list[d-1][0]+pc_list[d-1][1], pc_list[d-1][0])
    dfs_not_biggest_added(d-1, 0, 0)
    print(min(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N):
    start = i+A[i]
    if start > N-1:
        continue
    for j in range(start,N):
        if j == start + A[j]:
            ans+=1
print(ans)

### FIXED CODE ###

import numpy as np
from collections import Counter as cc
N = int(input())
A = list(map(int,input().split()))

ans = 0
A_p = cc(A+np.arange(N))
A_n = cc(np.arange(N) - A)
for k in range(1,N+1):
    ans += A_p[k]*A_n[k]
print(ans)
### BUGGY CODE ###

# D - Powerful Discount Tickets

def power(price, ticket_count):
    return int(price // (2 ** ticket_count))

# n: 商品数
# m: チケットの枚数
n, m = map(int, input().split())
data = list(map(int, input().split()))

ans = 0

for i in range(m):
    data.sort()
    data = data[::-1]

    max_data = data[0]
    if max_data == 0:
        break

    max_point = 0
    data[max_point] = power(data[max_point], 1)

print(sum(data))


### FIXED CODE ###

# D - Powerful Discount Tickets
import heapq

n, m = map(int, input().split())
data = list(map(int, input().split()))

pq = []

for i in data:
    heapq.heappush(pq, -i)

for _ in range(m):
    # 先頭の "最小値"
    p = heapq.heappop(pq)
    heapq.heappush(pq, -(-p // 2))

print(-sum(pq))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
for i in range(Q):
  B,C=map(int,input().split())
  for j in range(len(A)):
    if A[j]==B:
      A[j]=C
  s=0
  for k in range(len(A)):
    s=s+A[k]
  print(s)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
l=[0]*1000000
ans=sum(A)

for i in A:
  l[i]+=1

for i in range(Q):
  b,c=map(int,input().split())
  ans=ans+(c-b)*l[b]
  l[c]+=l[b]
  l[b]=0
  print(ans)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = [str(c) for c in input().strip()]

    ans = 0
    SS = []
    for i in range(N):
        si = S[i]
        d = {}
        for j in S[i+1:]:
            if j == si:
                continue
            if j in d:
                d[j] += 1
            else:
                d[j] = 1

        t = 1
        for k in d:
            t *= d[k] + 1

        ans += t

    print(ans % (10**9 + 7))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = [str(c) for c in input().strip()]

    ans = 0
    d = {}
    for i in range(N-1, -1, -1):
        s = S[i]
        if s in d:
            d[s] += 1
        else:
            d[s] = 1

        t = 1
        for k in d:
            if k == s:
                continue

            t *= d[k] + 1

        ans += t
    
    print(ans % (10**9 + 7))


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

import sys
input=sys.stdin.readline
n=int(input())
s=input().rstrip()
start=['SS','SW','WS','WW']
import sys
for k in range(4):
    ans=start[k]
    for i in range(2,n):
        if (ans[i-2:i]=='SS' and s[i-1]=='o') or (ans[i-2:i]=='SW' and s[i-1]=='x') or (ans[i-2:i]=='WS' and s[i-1]=='x') or (ans[i-2:i]=='WW' and s[i-1]=='o'):
            ans=ans+'S'
        else:
            ans=ans+'W'
    if (s[0]=='o' and ans[0]=='S') or (s[0]=='x' and ans[0]=='W'):
        if ans[1]==ans[n-1]:
            pass
        else:
            continue
    else:
        if ans[1]==ans[n-1]:
            continue
    if (s[n-1]=='o' and ans[n-1]=='S') or (s[n-1]=='x' and ans[n-1]=='W'):
        if ans[0]==ans[n-2]:
            pass
        else:
            continue
    else:
        if ans[0]==ans[n-2]:
            continue
    print(ans)
    sys.exit()
print(-1)
    




### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
s=input().rstrip()
start=['SS','SW','WS','WW']
import sys
for k in start:
    ans=[k[0],k[1]]
    for i in range(2,n):
        if (ans[i-2]=='S' and ans[i-1]=='S' and s[i-1]=='o') or (ans[i-2]=='S' and ans[i-1]=='W' and s[i-1]=='x') or (ans[i-2]=='W' and ans[i-1]=='S' and s[i-1]=='x') or (ans[i-2]=='W' and ans[i-1]=='W' and s[i-1]=='o'):
            ans.append('S')
        else:
            ans.append('W')
    if (s[0]=='o' and ans[0]=='S') or (s[0]=='x' and ans[0]=='W'):
        if ans[1]==ans[n-1]:
            pass
        else:
            continue
    else:
        if ans[1]==ans[n-1]:
            continue
    if (s[n-1]=='o' and ans[n-1]=='S') or (s[n-1]=='x' and ans[n-1]=='W'):
        if ans[0]==ans[n-2]:
            pass
        else:
            continue
    else:
        if ans[0]==ans[n-2]:
            continue
    for i in ans:
        print(i,end='')
    sys.exit()
print(-1)
### BUGGY CODE ###


from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[0 for b in range(N)] for a in range(N)]
#D = [[0 for b in range(N)] for a in range(N)]


for ab in AB:
  G[ab[0]-1][ab[1]-1] = 1
  G[ab[1]-1][ab[0]-1] = 1

def bfs(current, goal):
  q = deque([[current, 0]])
  memo = [0 for a in range(N)]
  while q:
    startcost = q.popleft()
    start = startcost[0]
    cost = startcost[1]
    if start == goal:
      return cost
    for i in range(N):
      if G[start][i] == 1 and memo[i] == 0:
        q.append([i, cost + 1])
        memo[i] = 1
  

distances = [0]
for i in range(N):
  count = 0
  for j in range(N):
    if G[i][j] == 1:
      count += 1
  if count == 1:
    aoki = bfs(i, v)
    takahashi = bfs(i, u)
    if aoki > takahashi:
      distances.append(aoki)

print(max(distances)-1)



### FIXED CODE ###

from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
AB = [list(map(int, input().split())) for a in range(N-1)]

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)
### BUGGY CODE ###

str_s = input()
int_k = int(input())

result = list()
for f in range(len(str_s)):
    pattern = set()
    if len(result) == int_k and str_s[f] > result[-1][0]:
        continue
    for t in range(f + 1, len(str_s) + 1):
        pattern.add(str_s[f:t])
        result = sorted(set(result + list(pattern)))[:int_k]

print(result[-1])



### FIXED CODE ###

str_s = input()
int_k = int(input())

result = list()
for f in range(len(str_s)):
    pattern = set()
    for t in range(f + 1, f + 1 + int_k):
        pattern.add(str_s[f:t])
        result = sorted(set(result + list(pattern)))[:int_k]

print(result[-1])
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()

def calculate(n, s):
    arr = list(s)

    rNum = arr.count("R")
    gNum = arr.count("G")
    bNum = arr.count("B")


    sum = 0

    for i in range(n):
        for j in range(i + 1, n):
            start = i
            middle = j
            end = i + (j - i) * 2
            if end > n - 1:
                break

            dict = {"R": False, "G": False, "B": False}
            dict.__setitem__(arr[start], True)
            dict.__setitem__(arr[middle], True)
            dict.__setitem__(arr[end], True)
            dictArr = np.array(list(dict.values()))
            if np.sum(dictArr == True) == 3:
                sum = sum + 1

    print(rNum*gNum*bNum - sum)


calculate(N, S)


### FIXED CODE ###

import math
N = int(input())
S = input()

# N = 39
# S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

def calculate(n, s):
    arr = list(s)

    rNum = arr.count("R")
    gNum = arr.count("G")
    bNum = arr.count("B")

    sum = 0

    for step in range(1,math.ceil(n / 2) + 1):
        for i in range(n - 2*step):
            s = "".join([arr[i],arr[i+step],arr[i+step*2]])
            if s == "RGB" or s == "RBG" or s == "BGR" or s == "BRG" or s == "GBR" or s == "GRB":
                sum = sum + 1


    print(rNum*gNum*bNum - sum)



calculate(N, S)
### BUGGY CODE ###

k = int(input())
s = 7
if k%2 == 0:
	print(-1)
elif k%5 == 0:
	print(-1)
else:
	while s%k != 0:
		s = 10*s+7
	s = str(s)
	print(len(s))

### FIXED CODE ###

import sys

k = int(input())

a = 0

for i in range(1, k+1):
	a = (a*10+7)%k
	if a == 0:
		print(i)
		sys.exit()
print(-1)
### BUGGY CODE ###

import fractions
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
ans = reduce(fractions.gcd, a)

for i in range(n):
    b = a[:i]+a[i+1:]
    ans = max(reduce(fractions.gcd, b), ans)

print(ans)

### FIXED CODE ###

import fractions

n = int(input())
a = list(map(int, input().split()))
ans = 0

l_gcd = [0]
for i in range(n):
    l_gcd.append(fractions.gcd(l_gcd[-1], a[i]))
# print(l_gcd)

r_gcd = [0]
for i in range(n):
    r_gcd.append(fractions.gcd(r_gcd[-1], a[-(i+1)]))
r_gcd.reverse()
# print(r_gcd)

for i in range(n):
    ans = max(ans, fractions.gcd(l_gcd[i], r_gcd[i+1]))
print(ans)
### BUGGY CODE ###

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

def prime_factor(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


ans = 0
for i in range(N):
    ans += prime_factor(A[i]).count(2)

print(ans)

### FIXED CODE ###

N = int(input())                                       
L = list(map(int, input().split()))
res = 0
for i in range(N):
    for j in range(30):
        if L[i]%(2**(30-j)) == 0:
            res += 30-j
            break
print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
N = int(input())
list = []
# 文字列の入力
for i in range(N):
    s = input()
    if not s in list:
        list.append(s)

#print(list)
print(len(list))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
N = int(input())
list = []
# 文字列の入力
for i in range(N):
    s = input()
    list.append(s)
    #if not s in list:
        #list.append(s)

#print(list)
print(len(set(list)))
### BUGGY CODE ###

R,C,K=map(int,input().split())
lis=[[0]*(C) for i in range(R)]
for i in range(K):
	a,b,c=map(int,input().split())
	lis[a-1][b-1]=c
dp=[[[0]*4 for i in range(C+1)]for j in range(R+1)]
for i in range(1,R+1):
	for j in range(1,C+1):
		for k in range(4):
			t=lis[i-1][j-1]
			dp[i][j][k]=max(dp[i-1][j][k],dp[i][j][k])
			dp[i][j][k]=max(dp[i][j-1][k],dp[i][j][k])
			if t!=0:
				
				dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+t)
				if k>0:
					dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+t)
print(max(dp[-1][-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
	R,C,K=map(int,input().split())
	lis=[[0]*(C) for i in range(R)]
	for i in range(K):
		a,b,c=map(int,input().split())
		lis[a-1][b-1]=c
	dp0=[[0]*(C+1) for i in range(R+1)]
	dp1=[[0]*(C+1) for i in range(R+1)]
	dp2=[[0]*(C+1) for i in range(R+1)]
	dp3=[[0]*(C+1) for i in range(R+1)]
	for i in range(1,R+1):
		for j in range(1,C+1):
			for x,y in ((dp0,0),(dp1,dp0),(dp2,dp1),(dp3,dp2)):
				t=lis[i-1][j-1]
				x[i][j]=max(x[i-1][j],x[i][j])
				x[i][j]=max(x[i][j-1],x[i][j])
				if t!=0:
					dp1[i][j]=max(dp1[i][j],x[i-1][j]+t)
					if y!=0:
						x[i][j]=max(x[i][j],y[i][j-1]+t)
	print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))
if __name__ == '__main__':
	main()
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [list(map(int, input().split())) for i in range(Q)]

    g = {}
    for a in A:
        if a not in g:
            g[a] = 1
        else:
            g[a] += 1

    for i in range(Q):
        B, C = tuple(BC[i])
        if B in g:
            t = g.pop(B)
            if C in g:
                g[C] += t
            else:
                g[C] = t
        ans = 0
        for k, v in g.items():
            ans += k * v
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [list(map(int, input().split())) for i in range(Q)]

    g = {}
    ans = 0
    for a in A:
        ans += a
        if a not in g:
            g[a] = 1
        else:
            g[a] += 1

    for i in range(Q):
        B, C = tuple(BC[i])
        if B in g:
            t = g.pop(B)
            ans += t * (C - B)
            if C in g:
                g[C] += t
            else:
                g[C] = t
        print(ans)


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

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = []
matrix_list2 = []
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            tap = [i,j]
            matrix_list1.append(tap)

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            tap = [x+1,y]
            matrix_list2.append(tap)
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            tap = [x-1,y]
            matrix_list2.append(tap)
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            tap = [x,y+1]
            matrix_list2.append(tap)
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            tap = [x,y-1]
            matrix_list2.append(tap)
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

s = input().split('T')
x, y = map(int, input().split())
x = abs(x-len(s[0]))
y = abs(y)
i = 0
j = 0
dx = []
for i in range(2, len(s), 2) :
    dx.append(len(s[i]))
dy = []
for i in range(1, len(s), 2) :
    dy.append(len(s[i]))

if sum(dx) < x or sum(dy) < y :
    print('No')
    exit()

xl = len(dx)
for i in range(1 << xl) :
    nx = 0
    for j in range(xl) :
        if i>>j & 1 :
            nx -= dx[j]
        else :
            nx += dx[j]
    if nx == x :
        break
else :
    print('No')

yl = len(dy)
for i in range(1 << yl) :
    ny = 0
    for j in range(yl) :
        if i>>j & 1 :
            ny -= dy[j]
        else :
            ny += dy[j]
    if ny == y :
        break
else :
    print('No')

print('Yes')

### FIXED CODE ###

s = input().split('T')
x, y = map(int, input().split())
s = [len(_) for _ in s]
dx = s[::2]
dy = s[1::2]

x = abs(x-dx[0])
y = abs(y)
dx = dx[1:]
px = 0
py = 0
for d in reversed(sorted(dx)) :
    if px > x :
        px -= d
    else :
        px += d

for d in reversed(sorted(dy)) :
    if py > y :
        py -= d
    else :
        py += d

if px == x and py == y :
    print('Yes')
else :
    print('No')
### BUGGY CODE ###

import heapq,sys

input=sys.stdin.readline

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

Q=int(input())
query=[]
for i in range(Q):
    v,d,c=map(int,input().split())
    query.append((v-1,d,c))
query=query[::-1]

ans=[0]*N
time=[-1]*N


for i in range(Q):
    v,d,c=query[i]
    que=[(0,v,d)]
    heapq.heapify(que)
    while que:
        val,v,di=heapq.heappop(que)
        time[v]=di
        if not ans[v]:
            ans[v]=c
        for nv in edge[v]:
            if di-1>time[nv]:
                time[nv]=di-1
                heapq.heappush(que,(val+1,nv,di-1))

for i in range(N):
    print(ans[i])

### FIXED CODE ###

import heapq,sys
from collections import deque

input=sys.stdin.readline

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

Q=int(input())
query=[]
for i in range(Q):
    v,d,c=map(int,input().split())
    query.append((v-1,d,c))
query=query[::-1]

ans=[0]*N
time=[-1]*N


for i in range(Q):
    v,d,c=query[i]
    que=deque([(0,v,d)])
    while que:
        val,v,di=que.popleft()
        time[v]=di
        if not ans[v]:
            ans[v]=c
        for nv in edge[v]:
            if di-1>time[nv]:
                time[nv]=di-1
                que.append((val+1,nv,di-1))

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import sys 
input=sys.stdin.readline
from collections import deque

N=int(input())
L=[[]]

for i in range(N):
    a=deque(map(int,input().split()))
    L.append(a)
#print(L)

day=0
cnt=0
for i in range(10**6+5):
    if cnt==N*(N-1)/2:
        break
    D=dict()
    CNT=0
    for j in range(1,N+1):
        #print(L[j],j)
        if len(L[j])==0 or j in D:
            continue
        elif L[L[j][0]][0]==j and L[j][0] not in D:
            D[j]=1
            D[L[j][0]]=1
            X=L[j][0]
            L[j].popleft()
            L[X].popleft()
            CNT+=1
    if CNT==0:
        print(-1)
        exit()
    cnt+=CNT
    day+=1
#print(L)
#print(cnt)
print(day)

### FIXED CODE ###

N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)