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

import sys
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
input = sys.stdin.readline
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append([i+1,N[j]])
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] != 0:
      None
    else:
      B[i] = 1
      if dp[i] == n-1:
        None
      else:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          break
        else:
          if B[miru] != 1:
            sie = dp[miru]
            if L[miru][sie][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              act += 1
            else:
              None
          else:
              None
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
if flag == False:
  print(-1)
else:
  print(cnt)

### FIXED CODE ###

import time
start = time.time()
n = int(input())
dp = [0]*n
cnt = 0
L = []
flag = True
for i in range(n):
  T = []
  N = list(map(int,input().split()))
  for j in range(n-1):
    T.append((i+1,N[j]))
  L.append(T)
while dp != [n-1]*n:
  B = [0]*n
  act = 0
  for i in range(n):
    if B[i] == 0:
      B[i] = 1
      if dp[i] != n-1:
        miru = L[i][dp[i]][1]-1
        if dp[miru] == n-1:
          flag = False
          dp = [n-1]*n
        else:
          if B[miru] != 1:
            if L[miru][dp[miru]][1] == i+1:
              dp[i] += 1
              dp[miru] += 1
              B[miru] = 1
              if act == 0:
                act = 1
  if act == 0:
    dp = [n-1]*n
    flag = False
  cnt += 1
  ela = time.time()-start
  if ela > 1.7:
    dp = [n-1]*n
if flag == False:
  print(-1)
else:
  if ela < 1.7:
    print(cnt)
  else:
    print(n*(n-1)//2)
### BUGGY CODE ###

from sys import stdin


def get_result(data):
    # N = int(data[0][0])
    S = data[1][0]
    ans = 0
    r_index = [i for i in range(len(S)) if S[i] == 'R']
    g_index = [i for i in range(len(S)) if S[i] == 'G']
    b_index = [i for i in range(len(S)) if S[i] == 'B']
    for i in r_index:
        for j in g_index:
            for k in b_index:
                s_i, s_j, s_k = sorted([i, j, k])
                if (s_j-s_i) != (s_k-s_j):
                    ans += 1
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    # N = int(data[0][0])
    S = data[1][0]
    r_index = [i for i in range(len(S)) if S[i] == 'R']
    g_index = [i for i in range(len(S)) if S[i] == 'G']
    b_index = set([i for i in range(len(S)) if S[i] == 'B'])
    all_case = len(r_index) * len(g_index) * len(b_index)
    invalid_case = 0
    for i in r_index:
        for j in g_index:
            s_i, s_j = sorted([i, j])
            tmp_max_b = s_j + (s_j-s_i)
            if tmp_max_b in b_index:
                invalid_case += 1
            tmp_min_b = s_i - (s_j-s_i)
            if tmp_min_b in b_index:
                invalid_case += 1
            tmp_mid_b = (s_i + s_j) / 2
            if tmp_mid_b in b_index:
                invalid_case += 1
    return all_case - invalid_case


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

import numpy as np
S = input()
S_list = []
for i in range(len(S)):
    S_list.append(int(S[i]))
S_list = np.array(S_list)
num = 0
for i in range(len(S_list)-3):
    #print(S_list[i], S_list[i+3])
    for j in range(i+3, len(S)):
        #print("\t", i, j, S_list[j], np.sum(S_list[i:j+1]))
        sum_temp = np.sum([v * np.power(10, k) for k, v in enumerate(S_list[i:j+1][::-1])])
        if sum_temp % 2019 == 0:
            num += 1
print(num)

### FIXED CODE ###

S = input()
N = len(S)
mod = 2019
num = [0 for i in range(2019)]
num[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    num[rem] += 1

print(int(sum([i * (i-1) / 2 for i in num])))
### BUGGY CODE ###

# encoding:utf-8

import numpy as np
import random
import copy

def select_ok(r_list,b_position):
    pass_list = []
    for i in range(len(r_list)):
        if r_list[i][0] < b_position[0] and r_list[i][1] < b_position[1]:
            pass_list.append(r_list[i])

    return pass_list



n = int(input())
r = []
b = []

for i in range(n):
    position = list(map(int, input().split()))
    r.append(position)

for i in range(n):
    position = list(map(int, input().split()))
    b.append(position)

b_sorted = sorted(b,key=lambda x:x[0])

answer = 0
for i in range(10000):
    r_2 = copy.copy(r)
    count = 0
    for i in range(n):
        # print(r)
        pass_list = select_ok(r_2,b_sorted[i])
        # pass_list_sorted = sorted(pass_list,key=lambda x:x[0])

        if len(pass_list) > 0:
            count += 1
            delete = random.choice(pass_list)
            r_2.remove(delete)

    answer = max(count,answer)
print(answer)


### FIXED CODE ###

# encoding:utf-8

import numpy as np
import random
import copy

def select_ok(r_list,b_position):
    pass_list = []
    for i in range(len(r_list)):
        if r_list[i][0] < b_position[0] and r_list[i][1] < b_position[1]:
            pass_list.append(r_list[i])

    return pass_list



n = int(input())
r = []
b = []

for i in range(n):
    position = list(map(int, input().split()))
    r.append(position)

for i in range(n):
    position = list(map(int, input().split()))
    b.append(position)

b_sorted = sorted(b,key=lambda x:x[0])
count = 0
for i in range(n):
    pairs = select_ok(r,b_sorted[i])
    if len(pairs) > 0:
        sorted_pairs = sorted(pairs,key=lambda x:x[1],reverse=True)
        # print(sorted_pairs)
        count += 1
        r.remove(sorted_pairs[0])

print(count)

# print(answer)
### BUGGY CODE ###

k,n =map(int,input().split())
mod = 998244353
fact=[1]*5000
for i in range(1,len(fact)):
  fact[i] = fact[i-1]*i%mod
def comb(n,k,p):
  if com[n][k] != -1:
    return com[n][k]
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=fact[n]
  b=fact[k]
  c=fact[n-k]
  yey = (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
  com[n][k] = yey
  return yey
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
com = [[-1] *4050 for i in range(4050)]
for i in range(2,2*k+1):
  ans = 0
  if i %2 == 1:
    pp = (i+1)//2
    pm = i - pp
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*power_func(2,q,mod)%mod
      if n - q<0:
        continue
      r = k-p*2
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)%mod
    print(ans%mod)
  else:
    pp = i//2 +1
    pm = i//2 -1
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*power_func(2,q,mod)%mod
      if n - q<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-1,n-q,mod)%mod
    for q in range(p+1):
      sen = comb(p,q,mod)*power_func(2,q,mod)%mod
      if n - q-1<0:
        continue
      r = k-p*2-1
      if r <0:
        r = 0
      ans += sen* comb(n+r-2,n-q-1,mod)%mod
    print(ans%mod)

### FIXED CODE ###

k,n =map(int,input().split())
mod = 998244353
fact = [1]*(n+k+1)
rfact = [1]*(n+k+1)
for i in range(n+k):
    fact[i+1] = rr = ((i+1) * fact[i]) % mod
    rfact[i+1] = pow(rr, mod-2, mod)
def comb(N, K,mod):
    return fact[N] * rfact[K] * rfact[N-K] % mod
kota = []
for i in range(2,k+2):
  ans = 0
  if i %2 == 1:
    pp = (i+1)//2
    pm = i - pp
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*pow(2,q,mod)%mod
      if n - q<0:
        break
      r = k-p*2
      if r <0:
        r = 0
      if n+r-1 < n-q:
        continue
      ans += sen* comb(n+r-1,n-q,mod)%mod
    kota.append(ans%mod)
  else:
    pp = i//2 +1
    pm = i//2 -1
    p = min(k-pp+1,pm)
    for q in range(p+1):
      sen = comb(p,q,mod)*pow(2,q,mod)%mod
      if n - q<0:
        break
      r = k-p*2-1
      if r <0:
        r = 0
      if n+r-1 < n-q:
        continue
      ans += sen* comb(n+r-1,n-q,mod)%mod
    for q in range(p+1):
      sen = comb(p,q,mod)*pow(2,q,mod)%mod
      if n - q-1<0:
        break
      r = k-p*2-1
      if r <0:
        r = 0
      if n+r-2 < n-q-1:
        continue
      ans += sen* comb(n+r-2,n-q-1,mod)%mod
    kota.append(ans%mod)
for i in kota:
  print(i)
for i in range(len(kota)-2,-1,-1):
  print(kota[i])
### BUGGY CODE ###

N, K = map(int, input().split())
for p in range(K):
  if (N - p) % K == 0 or (N + p) % K == 0:
    print(p)
    break

### FIXED CODE ###

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

A,B=map(int,input().split())

def int_to_bit(N):
  lst=[]
  ans=''
  if N==0:
    return 0
  while N!=1 and N!=0:
    lst.append(str(N%2))
    N//=2
  for i in range(1,len(lst)+1):
    ans+=lst[-i]
  if N==0:
    pass
  else:
    ans='1'+ans
  return int(ans)

def bit_to_int(N):
  N=str(N)
  ans=0
  for i in range(len(N)):
    ans+=int(N[i])*2**(len(N)-1-i)
  return ans

def XOR(a,b):
  a,b=min(a,b),max(a,b)
  a,b=str(a),str(b)
  length=len(a)
  lst=[]
  ans=''
  for i in range(1,length+1):
    if a[-i]==b[-i]=='1' or a[-i]==b[-i]=='0':
      lst.append('0')
    else:
      lst.append('1')
  for i in range(1,length+1):        # ここ下手
    ans+=lst[-i]
  if length==len(b):
    pass
  else:
    add=b[0:len(b)-length]
    ans=add+ans
  return ans

List=[A+i for i in range(B-A+1)]
while len(List)>1:
  v1=int_to_bit(List[0])
  v2=int_to_bit(List[1])
  v=bit_to_int(XOR(v1,v2))        # ここ下手
  List.pop(0)
  List.pop(0)
  List.insert(0,v)
  
print(List[0])

### FIXED CODE ###

A,B=map(int,input().split())

def int_to_bit(N):
  lst=[]
  ans=''
  if N==0:
    return 0
  while N!=1 and N!=0:
    lst.append(str(N%2))
    N//=2
  for i in range(1,len(lst)+1):
    ans+=lst[-i]
  if N==0:
    pass
  else:
    ans='1'+ans
  return int(ans)

def bit_to_int(N):
  N=str(N)
  ans=0
  for i in range(len(N)):
    ans+=int(N[i])*2**(len(N)-1-i)
  return ans

def XOR(a,b):
  a,b=min(a,b),max(a,b)
  a,b=str(a),str(b)
  length=len(a)
  lst=[]
  ans=''
  for i in range(1,length+1):
    if a[-i]==b[-i]=='1' or a[-i]==b[-i]=='0':
      lst.append('0')
    else:
      lst.append('1')
  for i in range(1,length+1):        
    ans+=lst[-i]
  if length==len(b):
    pass
  else:
    add=b[0:len(b)-length]
    ans=add+ans
  return bit_to_int(ans)

if A%2==0 and B%2==0:
  v=(B-A)//2
  if v%2==0:
    print(B)
  else:
    print(XOR(1,int_to_bit(B)))
elif A%2==0 and B%2==1:
  v=(B-A+1)//2
  if v%2==0:
    print(0)
  else:
    print(1)
elif A%2==1 and B%2==0:
  v=(B-1-A)//2
  if v%2==0:
    print(XOR(int_to_bit(A),int_to_bit(B)))
  else:
    print(XOR(1,int_to_bit(XOR(int_to_bit(A),int_to_bit(B)))))
else:
  v=(B-A)//2
  if v%2==0:
    print(A)
  else:
    print(XOR(int_to_bit(A),1))
### BUGGY CODE ###

n,m= map(int,input().split())
B = []
C = []
ans = 0
pna = 0
for i in range(m):
    A = list(map(str,input().split()))
    if A[1]=="AC":
        if A[0] not in B :
            B.append(A[0])
            ans += 1
            pna += C.count(A[0])
    if A[1]=="WA"  :
        C.append(A[0])
print(ans,pna)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)
### BUGGY CODE ###

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

mod=10**9+7
sum=0
for i in range(N-1):
    for j in range(i+1,N):
        sum+=((A[i] % mod)*(A[j] % mod))%mod
        sum=sum%mod
print(sum)

### FIXED CODE ###

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

mod=10**9+7

B=[0]
for i in range(1,N+1):
    B.append(A[i-1]+B[i-1])

ans=0
for i in range(N-1):
    ans+=A[i]*(B[N]-B[i+1])
    ans%=mod

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

X = int(input())
c = 0
for i in range(int(X/100)+1):
    for j in range(int((X-100*i)/101)+1):
        for k in range(int((X-100*i-101*j)/102) +1):
            for l in range(int((X-100*i-102*j-103*k)/103) +1):
                for m in range(int((X-100*i-101*j-102*k-103*l)/104)+1):
                    for n in range(int((X-100*i-101*j-102*k-103*l-104*m)/105)+1):
                        if 100*i + 101*j + 102*k + 103*l + 104*m + 105*n == X:
                            c = 1
                            
print(c)


### FIXED CODE ###

X= int(input())
val = X // 100
diff = X % 100
if diff <= 5*val:
    print(1)
else:
    print(0)
### BUGGY CODE ###

# 初期入力
N = int(input())
P = list(map(int, input().split()))

#　右から１つ目と２つ目だけ比較し分岐
count =1 # 一つ目（添え字０）は必ずOK
for i in range(1,N):
    if P[i-1] < P[i]: # 増えていたら×
        #print(P[i],P[:i+1])
        continue
    elif P[i] ==min(P[:i+1]): # 減っていてかつMinならOK
        #print(P[i],P[:i+1])
        count +=1
print(count)

### FIXED CODE ###

# 初期入力
N = int(input())
P = list(map(int, input().split()))

#　右から１つ目と２つ目だけ比較し分岐
count =1 # 一つ目（添え字０）は必ずOK
P_min = P[0]
for i in range(1,N):
    if P[i-1] < P[i]: # 増えていたら×
        #print(P[i],P[:i+1])
        continue
    elif P[i] <= P_min: # 今までのPで最小値ならOK
        #print(P[i],P[:i+1])
        count +=1
        P_min = P[i]
print(count)
### BUGGY CODE ###

from math import log2
def main():
    N = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    
    digits_cnt1 = [0]*60
    for ai in A:
        if ai == 0:
            continue
        #2**60-1みたいな時にfloatの桁落ちが生じるが、ai>>dが必ずfalseになるのでlist index out of rangeは生じない
        for d in range(int(log2(ai))+1):
            if ai>>d & 1:
                digits_cnt1[d] += 1
    
    ans = 0
    for i in range(60):
        ans += digits_cnt1[i]*(N-digits_cnt1[i])*pow(2,i,mod)
        ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from math import log
def main():
    N = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    
    digits_cnt1 = [0]*60
    for ai in A:
        if ai == 0:
            continue
        #2**60-1みたいな時にfloatの桁落ちが生じるが、元々の桁数を超えるとai>>dがfalseになるのでlist index out of rangeは生じない
        for d in range(int(log(ai)/log(2))+1):
            if ai>>d & 1:
                digits_cnt1[d] += 1
    
    ans = 0
    for i in range(60):
        ans += digits_cnt1[i]*(N-digits_cnt1[i])*pow(2,i,mod)
        ans %= mod
    print(ans)

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

from collections import deque
from itertools import product
def main():
    H, W = list(map(int, input().split()))
    A = [['#'] * (W + 2)] + [['#', ] + list(input()) + ['#', ] for _ in range(H)] + [['#'] * (W + 2)]
    DX = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = 0
    for h, w in product(range(1, H + 1), range(1, W + 1)):
        if A[h][w] == '.':
            count = 1
            for (dx, dy) in DX:
                stack = deque([[h, w]])
                while stack:
                    x, y = stack.popleft()
                    if A[x + dx][y + dy] == '.':
                        stack.append([x + dx, y + dy])
                        count += 1
                    else:
                        continue
            ans = max(ans, count)
        else:
            continue
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
def main():
    printl = lambda l: [print(x) for x in l]
    H, W = list(map(int, input().split()))
    A = np.array([[1 if i == '.' else 0 for i in input()] for _ in range(H)])
    L = np.zeros((H, W), dtype = np.int)
    R = np.zeros((H, W), dtype = np.int)
    U = np.zeros((H, W), dtype = np.int)
    D = np.zeros((H, W), dtype = np.int)
    L[:, 0] = A[:, 0]
    for w in range(1, W):
        L[:, w] = (L[:, w - 1] + 1) * A[:, w]
    R[:, W - 1] = A[:, W - 1]
    for w in range(W - 2, -1, -1):
        R[:, w] = (R[:, w + 1] + 1) * A[:, w]
    U[0, :] = A[0, :]
    for h in range(1, H):
        U[h, :] = (U[h - 1, :] + 1) * A[h, :]
    D[H - 1, :] = A[H - 1, :]
    for h in range(H - 2, -1, -1):
        D[h, :] = (D[h + 1, :] + 1) * A[h, :]
    print(np.max(L + R + U + D - 3))

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

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph,shortest_path,single_target_shortest_path
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())

# G.add_nodes_from(list(range(1,N+1)))
for _ in range(M):
    A,B = map(int,input().split())
    G.add_edge(A, B)

# shortestPath = shortest_path(G,target=1)
shortestPath = single_target_shortest_path(G,target=1)
# print(shortestPath)
if len(shortestPath) != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(shortestPath[i][1])

# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

from itertools import combinations
n = int(input())
a_ls = list(map(int, input().split()))
ans = 0
inds = [i for i in range(n)]
for ind_a, ind_b in combinations(inds, 2):
    Sum = a_ls[ind_a] + a_ls[ind_b]
    diff = abs(ind_a - ind_b)
    if Sum == diff:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a_ls = list(map(int, input().split()))
L_dict = defaultdict(int)
for i in range(n):
    Li = a_ls[i] + i + 1
    L_dict[Li] += 1

ans = 0
for j in range(n):
    Rj = j + 1 - a_ls[j]
    ans += L_dict[Rj]
print(ans)
### BUGGY CODE ###

# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い

N = int(input())
P = list(map(float, input().split()))
overhalf_N = (N+1)//2

dp = [[0]*(N+1) for _ in range(N+1)] # dp[i][j]：i枚で表がj枚になる確率
dp[0][0] = 1
for i in range(N):
  for j in range(min(i+1, overhalf_N)):
    dp[i+1][j+1] += dp[i][j] * P[i]
    dp[i+1][j] += dp[i][j] * (1-P[i])

print(1-sum(dp[N][:overhalf_N]))


### FIXED CODE ###

# dp[i][j]：i枚で表がj枚になる確率
# 1 - sum(:dp[N][(N+1)//2])を求めればいいため，dp[N][(N+1)//2:]は求める必要が無い
# jが大きい順に更新すればdp[i][j]のjを保持する必要はない

N = int(input())
P = list(map(float, input().split()))
overhalf_N = (N+1)//2
underhalf_N = overhalf_N - 1

dp = [0]*(N+1) # dp[N][j]：N枚で表がj枚になる確率

dp[0] = 1
for i in range(overhalf_N):
  pc = 1 - P[i]
  for j in range(i+1, 0, -1):
    dp[j] = dp[j-1] * P[i] + dp[j] * pc
  dp[0] = dp[0] * pc

for i in range(overhalf_N,N):
  pc = 1 - P[i]
  for j in range(underhalf_N, 0, -1):
    dp[j] = dp[j-1] * P[i] + dp[j] * pc
  dp[0] = dp[0] * pc

print(1-sum(dp[:overhalf_N]))
### BUGGY CODE ###


N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town =[1]
now_town=1
count = 0
check=False
for i in range(K):
    count =i+1
    if(A[now_town-1] in already_town):
        cicle_start_value=A[now_town-1]
        check=True
        break
    else:
        already_town.append(A[now_town-1])
        now_town = A[now_town-1]

if(check==False):
    print(now_town)
else:
    cicle_start=already_town.index(cicle_start_value)
    roop_town=already_town[cicle_start:]
    print(roop_town[(K-cicle_start)%((i+1)-cicle_start)])



### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town_check =[False]*(N+1)
already_town_check[1] = True
already_town = [1]
now_town=1
check=False
my_append = already_town.append
for i in range(K):
    check_town=A[now_town-1]
    if(already_town_check[check_town]):
        cicle_start_value=check_town
        check=True
        break
    already_town_check[check_town]=True
    my_append(check_town)
    now_town = check_town

if(check==False):
    print(now_town)
else:
    cicle_start=already_town.index(cicle_start_value)
    roop_town=already_town[cicle_start:]
    print(roop_town[(K-cicle_start)%((i+1)-cicle_start)])