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

import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
from collections import deque
import bisect
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def main():
    n,k=ints()
    a=ints()
    passed=[]
    flg=0
    p=0
    while flg==0:
        if p in passed:
            flg=1
            s=passed.index(p)
            break
        else:
            passed.append(p)
            p=a[p]-1
    l=len(passed)
    if k<l:
        print(passed[k]+1)
    else:
        print(passed[(k-s)%(l-s)+s]+1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
from collections import deque
import bisect
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def main():
    n,k=ints()
    a=ints()
    passed=[]
    flg=0
    p=0
    while flg==0:
        if a[p] == 'passed':
            flg=1
            s=passed.index(p)
            break
        else:
            passed.append(p)
            pp=p
            p=a[pp]-1
            a[pp]='passed'
    l=len(passed)
    if k<l:
        print(passed[k]+1)
    else:
        print(passed[(k-s)%(l-s)+s]+1)

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

mod = 10**9 + 7
n = int(input())
nums = list(map(int, input().split(" ")))

ans = 0

for i in range(n):
    for j in range(i+1, n):
        ans += nums[i] * nums[j]

print(ans % mod)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
nums = list(map(int, input().split(" ")))

ans = 0

ans = sum(nums) * sum(nums) - sum([num*num for num in nums])

print((ans // 2) % mod)
### BUGGY CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

def dfs(ns, prev, now, toru, results):
    end = defaultdict(int)
    k = cs[now]
    end[k] = 1
    s = 1 # nowで終わるパスの種類
    tmp_s2_sum = 0
    usList = defaultdict(list)
    for u in ns[now]:
        if u==prev:
            continue
        tmp_end, tmp_toru, tmp_s = results[u]  # dfs(ns, now, u, toru)
        for kk,vv in tmp_end.items():
            if kk!=k:
                end[kk] += vv
            usList[kk].append((vv, tmp_s))
        end[k] += tmp_s
        s += tmp_s
        tmp_s2_sum += tmp_s**2
    for kk,vv in usList.items():
        if kk!=k:
            x_sum = 0
            x2_sum = 0
            for item in vv:
                toru[kk] += (s - item[1]) * item[0]
                x_sum += item[0]
                x2_sum += item[0]**2
            toru[kk] -= (x_sum**2 - x2_sum) / 2
    toru[k] += (1 + ((s-1)**2 - tmp_s2_sum)/2 + (s-1))
#     print(now, prev, end, toru, s)
    results[now] = end, toru, s

toru = [0] * (n+1)
q = [(1, -1)] # now, prev
args = []
while q:
    u, prev = q.pop()
    args.append((u,prev))
    for v in ns[u]:
        if prev==v:
            continue
        q.append((v, u))
results = {}
for arg in args[::-1]:
    dfs(ns, arg[1], arg[0], toru, results)

for item in toru[1:]:
    print(int(item))

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
nums = []
total = 0
for i in range(N):
    A[i] = A[i] - (i+1)
    if A[i] not in nums:
        nums.append(A[i])
    total = total + A[i]

avg = (total/N)

'''
up = 0
down = 0
for i in range(N):
    if avg >= A[i]:
        down = down + 1
    else:
        up = up + 1


if down > up:
    if avg < 0:
        avg = int(avg) - 1
    else:
        avg = int(avg)
else:
    avg = round(avg)



sad = 0
for i in range(N):
    sad = sad + abs(A[i]-avg)
'''

l = [int(avg)-1,int(avg),int(avg) + 1]
sad = []
for i in range(3):
    tmp = 0
    for j in range(N):
        tmp = tmp + abs(A[j]-l[i])
    sad.append(tmp)

for i in range(len(nums)):
    tmp = 0
    for j in range(N):
        tmp = tmp + abs(A[j]-nums[i])
    sad.append(tmp)
    
print(min(sad))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

for i in range(N):
    A[i] = A[i] - (i+1)

A.sort()

medium = A[int(N/2)]

s = 0
for i in range(N):
    s = s + abs(A[i]-medium)

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

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        tmp[j] = min(tmp[j], d)
        tmp[j|c] = min(tmp[j|c], d+a)
    dp = tmp

print(dp[-1] if dp[-1]<INF else -1)


### FIXED CODE ###

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        if d < tmp[j]:
            tmp[j] = d
        if d+a < tmp[j|c]:
            tmp[j|c] = d+a
    dp = tmp

print(dp[-1] if dp[-1]<INF else -1)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()

dp = [ [0] * (len(T)+1)] + [[0]+[None]*len(T) for _ in range(len(S))]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + int(s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(S[x])
print(''.join(reversed(res)))





### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4011183

S,T = input(), input()
S,T = list(map(lambda x: ord(x)-97, S)), list(map(lambda x: ord(x)-97, T))

# print(S,T)

dp = [ [0] * (len(T)+1)] + [[0]+[None]*len(T) for _ in range(len(S))]

for i,s in enumerate(S):
    for j,t in enumerate(T):
        dp[i+1][j+1] = max(
                dp[i][j+1], 
                dp[i+1][j],
                dp[i][j] + (s==t)
                )
res = []

x,y = len(S), len(T)

while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        res.append(chr(S[x]+97))
print(''.join(reversed(res)))
### BUGGY CODE ###

N=int(input())
A=[]
c=0
B=[]
dellist=lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]
for i in range(N):
    A.append(int(input()))
while len(A)>0:
    for j in range(len(A)):
        if A[0]<A[j]:
            B.append(j)
    B.append(0)
    A=dellist(A,B)
    c+=1
    B=[]
print(c)

### FIXED CODE ###

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

n = int(input())
a = [int(input()) for _ in range(n)]

s = deque([a[0]])

from bisect import bisect_left

for i in a[1:]:
    if i <= s[0]:
        s.appendleft(i)
    else:
        s[bisect_left(s, i) - 1] = i

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

s = input()
q = int(input())
o = 0

for _ in range(q):
    qu = list(input().split())
    if len(qu) == 1:
        o = -1 if o == 0 else 0
    if len(qu) == 3:
        if qu[1] == '1':
            s = qu[2] + s if o == 0 else s + qu[2]
        if qu[1] == '2':
            s = s + qu[2] if o == 0 else qu[2] + s

print(s) if o == 0 else print(s[::-1])


### FIXED CODE ###

from collections import deque
S = list(input()) 
d = deque()
for s in S:
    d.append(s)
q = int(input())
o = 0

for _ in range(q):
    qu = list(input().split())
    if len(qu) == 1:
        o = -1 if o == 0 else 0
    if len(qu) == 3:
        if qu[1] == '1':
            d.appendleft(qu[2]) if o == 0 else d.append(qu[2])
        if qu[1] == '2':
            d.append(qu[2]) if o == 0 else d.appendleft(qu[2])

r = ''
if o == 0:
    for _ in range(len(d)):
        r += d.popleft()
else:
    for _ in range(len(d)):
        r += d.pop()

print(r)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
total=0
a=0
b=0
for h in range(N-1):
    for i in range(h+1,N):
        a+=A[i]
    b+=A[h]*a
    a=0
print(b%1000000007)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
total=0
ans=0
d=[0]*210000

for i in range(N):
    total+=A[i]
    d[i]=total

for j in range(N):
    ans+=A[j]*(total-d[j])

print(ans%1000000007)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
m=10**9+7
if N%2==0:
  if A.count(0)!=0:
    print(0)
    exit()
  for j in range(1,N//2+1):
    if A.count(2*j-1)!=2:
      print(0)
      exit()
else:
  if A.count(0)!=1:
    print(0)
    exit()
  for i in range(1,N//2+1):
    if A.count(2*i)!=2:
      print(0)
      exit()
print((2**(N//2))%m)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[0]*N
for j in A:
  B[j]+=1
m=10**9+7
if N%2==0:
  if B[0]!=0:
    print(0)
    exit()
  for j in range(1,N//2+1):
    if B[2*j-1]!=2:
      print(0)
      exit()
else:
  if B[0]!=1:
    print(0)
    exit()
  for i in range(1,N//2+1):
    if B[2*i]!=2:
      print(0)
      exit()
print((2**(N//2))%m)
### BUGGY CODE ###

# coding: utf-8
def main():
    N,Q = map(int, input().split())
    s = input()
    Golem_list = [1] * N
    ans = N
    char_list = {}
    for si in range(len(s)):
        if s[si] in char_list:
            char_list[s[si]].append(si)
        else:
            char_list[s[si]] = [si]

    # print(char_list)

    for i in range(Q):
        # 呪文
        t,d = input().split()
        if t in char_list:
            tlist = char_list[t]
            for si in tlist:
                ans = move(Golem_list,d,ans,N,si)
    print(ans)


def move(Golem_list,d,ans,N,si):
    if d == 'L':
        if si == 0:
            ans -= Golem_list[0]
            Golem_list[0] = 0
        else :
            Golem_list[si-1] += Golem_list[si]
            Golem_list[si] = 0

    elif d == 'R':
        if si == N-1:
            ans -= Golem_list[N-1]
            Golem_list[N-1] = 0
        else :
            Golem_list[si+1] += Golem_list[si]
            Golem_list[si] = 0
    # print(Golem_list)
    # print("#"+str(ans))
    return ans

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding: utf-8
def main():
    N,Q = map(int, input().split())
    s = input()
    ans = N
    command = []

    # print(char_list)

    for i in range(Q):
        t,d = input().split()
        command.append([t,d])

    r = binary_serch_R(command,s,N)
    #print(r)
    l = binary_serch_L(command,s,N)
    #print(l)
    ans = ans - (N-r) - (l+1)
    if ans < 0:
        ans = 0
    print(ans)

def simulation_R(command,s,now,N):
    for pair in command:
        if pair[0] == s[now]:
            if pair[1] == 'L':
                now -= 1
            elif pair[1] == 'R':
                now += 1
        if now < 0:
            return False
        elif now >= N:
            return True
    return False

def simulation_L(command,s,now,N):
    for pair in command:
        if pair[0] == s[now]:
            if pair[1] == 'L':
                now -= 1
            elif pair[1] == 'R':
                now += 1
        if now < 0:
            return True
        elif now >= N:
            return False
    return False


def binary_serch_R(command,s,N):
    left = 0
    right = N-1
    if simulation_R(command,s,left,N) :
        return -1
    if simulation_R(command,s,right,N) == False:
        return N

    while abs(right - left) > 1:
        mid = int((left+right)/2)
        # print(mid)
        if simulation_R(command,s,mid,N) :
            right = mid
        else :
            left = mid 
    return right

def binary_serch_L(command,s,N):
    left = 0
    right = N-1
    if simulation_L(command,s,left,N) == False :
        return -1
    if simulation_L(command,s,right,N):
        return N
        
    while abs(right-left) > 1:
        mid = int((left+right)/2)
        if simulation_L(command,s,mid,N) :
            left = mid
        else :
            right = mid 
    return left

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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    # W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

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

    mod = 1000000007

    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                #dp[next] %= mod

    print(dp[N] % mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M = list(map(int, input().split()))
    A = set()
    for i in range(M):
        A.add(int(input()))

    mod = 1000000007

    dp = [0] * (N+1)
    dp[0] = 1
    for now in range(0, N):
        for next in range(now+1, min(N, now+2)+1):
            if next not in A:
                dp[next] += dp[now]
                dp[next] %= mod

    print(dp[N] % mod)

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

N=int(input())
S={}
SS=[]
answer=0
for _ in range(N):
    s=input()
    s=sorted(s)
    s=str(s)
    if s in SS:
        answer+=S[s]
        S[s] += 1
    else:
        SS.append(s)
        S[s]=1
print(answer)


### FIXED CODE ###

import collections
N=int(input())
SS=[]
answer=0
for _ in range(N):
    s=input()
    s=sorted(s)
    S=''
    for a in s:
        S+=a
    SS.append(S)
a=collections.Counter(SS)
for n in a.values():
   answer+=(n-1)*n/2
print(int(answer))
### BUGGY CODE ###

from collections import deque
import numpy as np

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
S = []
for i in range(H):
    S.append(input())


def exists(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    elif S[h][w] == "#":
        return False
    else:
        return True


costs = -1 * np.ones((H, W), dtype=np.int)
passed = np.zeros((H, W), dtype=np.int)
costs[C_h - 1, C_w - 1] = 0
d = deque()
d.append((C_h - 1, C_w - 1))
while d:
    h, w = d.popleft()
    c = costs[h, w]
    if passed[h, w] == 1:
        continue
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if exists(hh, ww):
            if (hh, ww) in d:
                d.remove((hh, ww))
            costs[hh, ww] = c
            d.appendleft((hh, ww))
    for i in range(5):
        for j in range(5):
            hh = h + i - 2
            ww = w + j - 2
            if exists(hh, ww):
                if costs[hh, ww] == -1:
                    costs[hh, ww] = c + 1
                    d.append((hh, ww))
    passed[h, w] = 1
print(costs[D_h - 1, D_w - 1])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
W_ = W + 4
H_ = H + 4
S = ["#" * W_] * 2 + ["##" + input() + "##" for _ in range(H)] + ["#" * W_] * 2

INF = float('inf')
costs = [[INF] * W_ for _ in range(H_)]
costs[C_h + 1][C_w + 1] = 0
d0 = deque()
d0.append((C_h + 1, C_w + 1, 0))
d1 = deque()
while d0:
    h, w, c = d0.popleft()
    d1.append((h, w, c))
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if S[hh][ww] == '.' and c < costs[hh][ww]:
            costs[hh][ww] = c
            d0.appendleft((hh, ww, c))
    if len(d0) == 0:
        while d1:
            h, w, c = d1.popleft()
            for i in range(5):
                for j in range(5):
                    hh = h + i - 2
                    ww = w + j - 2
                    if S[hh][ww] == '.' and c + 1 < costs[hh][ww]:
                        costs[hh][ww] = c + 1
                        d0.append((hh, ww, c + 1))

if costs[D_h + 1][D_w + 1] != INF:
    ans = costs[D_h + 1][D_w + 1]
else:
    ans = -1
print(ans)
### BUGGY CODE ###

from collections import Counter

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

ans = 0
for a in A:
    ans += L * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    h2 = []
    heapq.heapify(h)
    for i in range(n):
        heapq.heappush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = heapq.heappop(h)
        i=-i
        temp = i-a[j]
        sho=temp//(b[j-1]+b[(j+1)%n])
        if  sho==0:
            h2.append((i, j))
            continue
        cnt += sho
        b[j] -= (b[j-1]+b[(j+1)%n])*sho
        heapq.heappush(h, (-b[j], j))
    h2.sort(key=lambda x: x[1])
    for i in range(n):
        if a[i] != h2[i][0]:
            print(-1)
            return 0
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

def resolve():
    n = int(input())
    am = []
 
    from collections import deque
 
    for i in range(n):
        am.append(deque(list(map(lambda x: int(x) - 1, input().split()))))
 
    cnt = n * (n - 1) // 2
 
    day = 0
    while cnt > 0:
        day += 1
        match = 0
        done = {}
        for i in range(n):
            if i in done:
                continue
            if len(am[i]) == 0:
                continue
            j = am[i][0]
            if j not in done and am[j][0] == i:
                am[i].popleft()
                am[j].popleft()
                done[i] = 1
                done[j] = 1
                match += 1
 
        if match == 0:
            print(-1)
            return
        else:
            cnt -= match
 
    print(day)
    
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    a = []

    for i in range(n):
        row = list(map(lambda x: int(x) - 1, input().split()))
        row.reverse()
        a.append(row)

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

    for i in range(n):
        check(i)

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

        for p in prev_q:
            (i, j) = p
            check(i)
            check(j)

    for i in range(n):
        if len(a[i]) != 0:
            print(-1)
            return
    print(day)
    
resolve()