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

# -*- coding: utf-8 -*-

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

# 最短経路(仮)の全長
sm = 0
for i in range(N):
    for j in range(i+1, N):
        sm += A[i][j]

# ワーシャルフロイドで全頂点の最短距離
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 最短 > 経由 があればNG
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            # 最短 = 経由 があるなら、経由を使えば全長を減らせる
            elif A[i][j] == A[i][k] + A[k][j] and j != k and i != k and i < j:
                # 最短経路(仮)から直行ルートをなくす
                sm -= A[i][j]
print(sm)


### FIXED CODE ###

# -*- coding: utf-8 -*-

from copy import deepcopy

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

# ワーシャルフロイドで全頂点の最短距離
B = deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 最短 > 経由 があればNG
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            # 最短 = 経由 があるなら、経由を使えば全長を減らせる
            elif A[i][j] == A[i][k] + A[k][j] and j != k and i != k and i < j:
                # 最短経路(仮)から直行ルートをなくす
                B[i][j] = 0

# 削減された最短経路の全長
sm = 0
for i in range(N):
    for j in range(i+1, N):
        sm += B[i][j]
print(sm)
### BUGGY CODE ###

N, K = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = [0 for i in range(K)]
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    ans += rem_count[A[i] % K]
    rem_count[A[i] % K] += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = list(map(int, input().strip().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

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

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None]*n
dp[0], dp[1] = 0, abs(h[0]-h[1])
for i in range(2, n):
    di = 10**9
    hi = h[i]
    for j in range(max(0, i-k), i):
        dj = dp[j] + abs(h[j]-hi)
        if di > dj:
            di = dj
    dp[i] = di
print(dp[-1])

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = 10**10
    dp = [inf]*n
    dp[0] = 0
    for i, (di, hi) in enumerate(zip(dp[1:], h[1:]), 1):
        num = max(i-K, 0)
        for dk, hk in zip(dp[num:i], h[num:i]):
            a = dk+abs(hi-hk)
            if di > a:
                di = a
        dp[i] = di
    print(dp[n-1])

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

N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
tmp = [1]
import time
start = time.time()
flag = True
while 0 in ans[2:]:
  #print(ans)
  for i in tmp:
    #print('i',i)
    next = g[i]
    #print('next',next)
    for j in next:
      if ans [j] == 0:
        ans[j] = i
  tmp = next
  if time.time() - start > 1.99:
    flag = False
    print('No')
    break
if flag:
  print('Yes')
  for i in range(2,N+1):
    print(ans[i])

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])
### BUGGY CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process
daysL = [0]*(N+1)
daysR = [0]*(N+1)
tR = 1
tL = K
for i in range(N):
    if S[i] == 'o' and sum(daysL[max(0,i-C+1):i+1]) == 0:
        daysL[i+1] = tR
        tR += 1
    else:
        daysL[i+1] = 0

    j = N-i
    if S[j-1] == 'o' and sum(daysR[j:min(N+1,j+C)]) == 0:
        daysR[j-1] = tL
        tL -= 1
    else:
        daysR[j-1] = 0

# output
# print(daysL)
# print(daysR)
if max(daysL) == K:    
    for i in range(N):
        if S[i] == 'o' and daysL[i+1] != 0 and daysL[i+1] == daysR[i]:
            print(i+1)


### FIXED CODE ###

# input
N, K, C = map(int, input().split())
S = input()

# process
l = [i+1 for i in range(N) if S[i] == 'o']
left = [l[0]]
right = [l[-1]]
for i in range(1, len(l)):
    if l[i] > left[-1]+C:
        left.append(l[i])
    if l[-i-1] < right[-1]-C:
        right.append(l[-i-1])

# output
# print(l)
# print(left)
# print(right)
if len(left) == K:
    for i in range(len(left)):
        if left[i] == right[-i-1]:
            print(left[i])
### BUGGY CODE ###

a,b = map(int,input().split())
import fractions
def disjoint_cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            for c in cf:
                if fractions.gcd(c,i) != 1:
                    break
            else:
                cf.append(i)
                continue
    return cf

cf = disjoint_cf(a,b)
print(len(cf) + 1)


### FIXED CODE ###

a,b = map(int,input().split())
import fractions
import collections
import copy
def prime_factorization(n):
    a = [1]
    n1 = copy.deepcopy(n)
    while n % 2 == 0:
        n //= 2
    if n1 != n:
        a.append(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            n //= f
            if a[-1] != f:
                a.append(f)
        else:
            f += 2
    if a[-1] != n and n != 1:
        a.append(n)
    return a
print(len(prime_factorization(fractions.gcd(a,b))))
### BUGGY CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  for i in range(l,r):
    dp.update(i,min(dp.get(l-1,i)+c,dp.get(i)))
print(dp.get(N-1) if dp.get(N-1) != INF else -1)


### FIXED CODE ###

class SegmentTree:
  def __init__(self, size, default, op = min):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

N,M = map(int,input().split())
LRC = [list(map(int,input().split())) for _ in range(M)]
LRC.sort(key=lambda x:(x[0],x[1]))
#print(LRC)

INF = 10**18
dp = SegmentTree(N,INF,min)
dp.update(0,0)
#print(dp.get(0,1))

for l,r,c in LRC:
  p = dp.get(l-1,r-1)+c
  # cf.https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/1109_nikkei2019-2-qual
  #for i in range(l,r):
  #  if p < dp.get(i):
  #    dp.update(i,p)
  if p < dp.get(r-1):
    dp.update(r-1,p)
print(dp.get(N-1) if dp.get(N-1) != INF else -1)
### BUGGY CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)
B = [[A[i], F[i]] for i in range(N)]
t = A[N-1] * F[N-1]
B.sort(key=lambda x: x[0]*x[1])

for x in range(B[N-1][0]*B[N-1][1]):
    table = [0]*N
    for i in range(N):
        if B[i][0]*B[i][1] > x:
            k = x // B[i][1]
            table[i] = max(B[i][0] - k, 0)
    if sum(table) <= K:
        print(x)
        break


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

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

dp = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
    s = a[i]
    for j in range(i + 1, n):
        k = []
        s += a[j]
        for d in range(i, j):
            k += [dp[i][d] + dp[d + 1][j]]
        dp[i][j] = min(k) + s
print(dp[0][-1])


### FIXED CODE ###

def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

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

if K == 1:
  print(0)
  sys.exit()

seen = [N]
x = N
while True:
  x = abs(x-K)
  if x == 1:
    print(1)
    sys.exit()
  if x in seen:
    print(min(seen))
    sys.exit()
  else:
    seen.append(x)


### FIXED CODE ###

N, K = list(map(int, input().split()))
n = N%K
print(min(n, abs(K-n)))
### BUGGY CODE ###

n = int(input())
list = list(map(int, input().split()))
list.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if list[i] + list[j] <= list[k]:
                break
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
list = list(map(int, input().split()))
list.sort()
import bisect
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        index = bisect.bisect_left(list, list[i]+list[j])
        ans += index - j -1
print(ans)
### BUGGY CODE ###

a,b,x = (int(i) for i in input().split())

count = 0
for i in range(a,b+1):
    if i%x==0:
        count = count+1

print(count)

### FIXED CODE ###

a,b,x = (int(i) for i in input().split())

ika = (a-1)//x
zenbu = b//x

print(zenbu - ika)
### BUGGY CODE ###

N = int(input())
A = [input() for _ in range(N)]
for i in range(N):
    print(max(A[0:i]+A[i+1:len(A)]))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A_max = max(A)
a = A.index(A_max)
A.sort(reverse=True)
for i in range(N):
    if i == a:
        print(A[1])
    else:
        print(A[0])
### BUGGY CODE ###

def f(k):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi1[0] = s = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
        dpi=dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(k))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

s=input()
q= int(input())

for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		s=s[::-1]
	else:
		if t[1]=='1':
#			s=t[2]+s
#			s=f"{t[2]}{s}"
			list1=[t[2],s]
			s="".join(list1)
		else:
#			s=s+t[2]
#			s=f"{s}{t[2]}"   
			list2=[s,t[2]]
			s="".join(list2)

print (s)

### FIXED CODE ###

s=input()
q= int(input())

top=""
btm=""

iturn=0
for iq in range(1,q+1):
	t=input().split()
	if t[0]=='1':
		iturn=iturn+1   	
	else:
		iturn2=iturn%2
		if (t[1]=='1' and iturn2==0) or (t[1]=='2' and iturn2==1):
#			s=t[2]+s
#			s='{}{}'.format(t[2],s)
			top=t[2]+top
		else:
#			s=s+t[2]
#			s='{}{}'.format(s,t[2])
			btm=btm+t[2]

if iturn%2==0:
	s=top+s+btm
else:
	s=btm[::-1]+s[::-1]+top[::-1]
print (s)
### BUGGY CODE ###

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

while len(A) > 1:
    a = min(A)
    A = set(x - a if x != a else a for x in A)
    if 1 in A:
        A = {1}
print(list(A)[0])

### FIXED CODE ###

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

while len(A) > 1:
    a = min(A)
    A = set(x % a if x % a != 0 else a for x in A)
    if 1 in A:
        A = {1}
print(list(A)[0])
### BUGGY CODE ###

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

import itertools

sum = 0
for i, j in itertools.combinations(A, 2):
    sum += i * j

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

### FIXED CODE ###

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

mod = 10**9 + 7

print(((sum(A)**2 - sum([i**2 for i in A]))//2) % mod)
### BUGGY CODE ###

s = input()
q = int(input())

#一番最後に1度だけ反転すればよい
reverse_count = 0
for i in range(q):
  y = input().split()
  if y[0] == '1':
    #反転は最後に行う
    reverse_count += 1
    continue
  elif y[0] == '2':
    if y[1] == '1':
      #文字列の先頭に追加。反転回数が奇数なら、末尾に追加と同義
      if reverse_count % 2 == 1:
        s = s + y[2]
      else:
        s = y[2] + s
    elif y[1] == '2':
      #文字列の末尾に追加。反転回数が奇数なら、先頭に追加と同義
      if reverse_count % 2 == 1:
        s = y[2] + s
      else:
        s = s + y[2] 

#最後に一度だけ反転させる
if reverse_count % 2 == 0:
  #元の順序に戻るので、そのまま
  print(s)
else:
  print(s[::-1])



### FIXED CODE ###

from collections import deque
#双方向リストにするため、dequeを使用する
#（先頭と末尾に文字を追加するため）
s = deque(input())
q = int(input())

#一番最後に1度だけ反転すればよい
reverse_count = 0
for i in range(q):
  y = input().split()
  if y[0] == '1':
    #反転は最後に行う
    reverse_count += 1
    continue
  elif y[0] == '2':
    if y[1] == '1':
      #文字列の先頭に追加。反転回数が奇数なら、末尾に追加と同義
      if reverse_count % 2 == 1:
        s.append(y[2])
      else:
        s.appendleft(y[2])
    elif y[1] == '2':
      #文字列の末尾に追加。反転回数が奇数なら、先頭に追加と同義
      if reverse_count % 2 == 1:
        s.appendleft(y[2])
      else:
        s.append(y[2])

#最後に一度だけ反転させる
if reverse_count % 2 == 0:
  #元の順序に戻るので、そのまま
  print("".join(s))
else:
  s.reverse()
  print("".join(s))
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    l = input()
    if l == "1":
        S = S[::-1]
    elif len(l) > 1:
        t, f, c = l.split()
        if f == "1":
            S = c + S
        else:
            S = S + c

print(S)




### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
re_flag = False 
start = deque()
finish = deque()
for i in range(Q):
    l = input()
    if l == "1":
        re_flag = not bool(re_flag)
    else:
        t, f, c = l.split()
        if f == "1":
            if re_flag:
                finish.append(c)
            else:
                start.append(c)
        else:
            if re_flag:
                start.append(c)
            else:
                finish.append(c)

S.extend(finish)
S.extendleft(start)

ans = deque()
if re_flag:
    ans.extendleft(S)
else:
    ans = S

print("".join(list(ans)))
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))

c=0
from itertools import combinations

combs = list(combinations(l, 3))

for comb in combs:
    if comb[0] < comb[1] + comb[2]:
        if comb[1] < comb[2] + comb[0]:
            if comb[2] < comb[0] + comb[1]:
                c += 1
print(c)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l = sorted(l)

c=0

import bisect

for i in range(n-2):
    for j in range(i+1, n-1):
        c += bisect.bisect_left(l, l[i]+l[j]) - j - 1
print(c)
### BUGGY CODE ###

import heapq
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()

A=[0]*m
heapq.heapify(A)
#日がたつごとに選択肢が少なくなる→後ろから見ていく
ans=0
for day in range(m):
    for a,b in ab:
        if a<day+1:continue
        if a==day+1:
            heapq.heappush(A,-b)
        else:
            temp=heapq.heappop(A)
            ans+=temp
            #print(temp)
            break
    else:
        ans+=heapq.heappop(A)
print(-ans)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
heapq.heapify(l)
a=[]
heapq.heapify(a)
fd=heapq.heappop(l)
heapq.heappush(a,-fd[1])
ans=0
for day in range(fd[0],m+1):
    while l:
        temp=heapq.heappop(l)
        if temp[0]>day:
            heapq.heappush(l,temp)
            break
        else:
            heapq.heappush(a,-temp[1])
    if a:
        ans+=heapq.heappop(a)
print(-ans)
### BUGGY CODE ###

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

st = m//n

for i in range(st, 0, -1):
    mod = m - n*i
    if mod % i == 0:
        print(i)
        break

### FIXED CODE ###

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

st = m//n

for i in range(st, 0, -1):
    mod = m - n*i
    if mod % i == 0:
        print(i)
        break
### BUGGY CODE ###

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

for i in range(M):
    ind = A.index(max(A))
    A[ind] = max(A)//2
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)
for i in range(M):
    max_ = heapq.heappop(A)
    max_ = -max_//2
    heapq.heappush(A, -max_)
print(-sum(A))
### BUGGY CODE ###

# UnionFindの利用とreverseの発想まではOKだがTLE


class UnionFind(object):

    def __init__(self, N):
        self._tree = [i for i in range(N)]
        self._rank = [0] * (N + 1)

    def find(self, x):
        if self._tree[x] == x:
            return x
        else:
            self._tree[x] = self.find(self._tree[x])
            return self._tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # ランクを考慮しない場合はどちらが親になっても良い
        if self._rank[x] < self._rank[y]:
            self._tree[x] = y
        else:
            self._tree[y] = x

        if self._rank[x] == self._rank[y]:
            self._rank[x] += 1

    def has_same_parent(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
A_B = [tuple(map(int, input().split())) for _ in range(M)]


def calc_inconvenience(unionfind, N):
    inconvenience = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if not unionfind.has_same_parent(i, j):
                inconvenience += 1
    return int(inconvenience / 2)


result = list()
unionfind = UnionFind(N + 1)
for a, b in reversed(A_B):
    result.append(calc_inconvenience(unionfind, N))
    unionfind.unite(a, b)
for r in reversed(result):
    print(r)




### FIXED CODE ###

class UnionFind(object):

    def __init__(self, N):
        self._tree = [i for i in range(N)]
        self._rank = [0] * (N + 1)
        self.size = [1] * N
        self.inconvenience = N * (N - 1) // 2

    def find(self, x):
        if self._tree[x] == x:
            return x
        else:
            self._tree[x] = self.find(self._tree[x])
            return self._tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        self.inconvenience -= self.size[x] * self.size[y]
        if self._rank[x] < self._rank[y]:
            self._tree[x] = y
            self.size[y] += self.size[x]
        else:
            self._tree[y] = x
            self.size[x] += self.size[y]

        if self._rank[x] == self._rank[y]:
            self._rank[x] += 1


N, M = map(int, input().split())
A_B = [tuple(map(int, input().split())) for _ in range(M)]

result = list()
uf = UnionFind(N)
for a, b in reversed(A_B):
    result.append(max(0, uf.inconvenience))
    uf.unite(a - 1, b - 1)
for r in reversed(result):
    print(r)
### BUGGY CODE ###


def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] + A

    seen = {}
    cnt = 0
    dst = 1
    while K:
        if dst in seen:
            cycle = cnt - seen[dst]
            K %= cycle
            seen = {}
        else:
            seen[dst] = cnt

        dst = A[dst]
        cnt += 1
        K -= 1

    print(dst)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A = [0] + A

    seen = {}
    find_cnt = {}
    cnt = 0
    dst = 1
    while K:
        if dst in seen:
            cycle = cnt - seen[dst]
            K %= cycle
            print(find_cnt[seen[dst]+K])
            return

        else:
            seen[dst] = cnt
            find_cnt[cnt] = dst

        dst = A[dst]
        cnt += 1
        K -= 1

    print(dst)


if __name__ == "__main__":
    main()