Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())

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

ex = 1
for i in range(N+10):
    ex = A[ex - 1]
    if ex == 1:
        rp = i+1
        Z = K % rp
        break
    else:
        i += 1


ans = 1
for k in range(Z):
    ans = A[ans - 1]
    k = k + 1
    
    
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
ans = 1
c = 1
while ans:
  b = A[c-1]
  c = A[b-1]
  c.append(B)
  if c == b:
    B = B*k
    break
print(B[k-1])

Submission status: Runtime Error

Solution code:
import itertools
from collections import defaultdict
import collections
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

tf = [False] * (n + 1)
tf[1] = True
ss = [1]
cnt = 0
while cnt < k:
    if len(ss) != 1 and tf[a[ss[cnt] - 1]]:
        d = a[ss[cnt] - 1]
        break
    tf[a[ss[cnt] - 1]] = True
    ss.append(a[ss[cnt] - 1])
    cnt += 1


sss = ss.index(d)
print(ss[sss+(k -len(ss)) % (len(ss) - sss)])
    # print(ss.index(d))
    # print(ss[k % (len(ss) - ss.index(d))])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
lst=[0]
now=0
memo=0
town=[0]*n
town[0]=1
b=0
for i in range(k):
	now=a[now]
	if town[now]==1:
		memo=now
		b=1
		break
	lst.append(now)
	town[now]=1
if b==1:
	i=a.index(memo)
	l=len(lst)
	if memo!=0:
		lst=lst[i:]
	print(lst[(k-l)%len(lst)]+1)
else:
	print(now)

Submission status: Runtime Error

Solution code:
z = 0

b = [1]
for i in range(1000000):
  j = [a[b[i]-1]]
  b.extend(j)

for i in range(n):
  if b.count(i+1)>=3:
    z = z + 1

if k <= n:
  y = b[k]
else:
  l = (k-n)%z
  y = b[n+l]
print(y)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
if len(l) > k-1:
    print(l[k])
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])

Submission status: Runtime Error

Solution code:
n,K=list(map(int,input().split()))
a = list(map(int,input().split()))
b = []
c = [0]*len(a)
I=0
check=0
k=0
if a[k]==1:
    print(1)
else:
    for i in range(n):
        b.append(a[k])
        tes=a[k]
        k=a[k]-1
        if a[k]==1:
            b.append(1)
            check=-1
            break
        else:
            if c[a[k]-1]==0:
                c[a[k]-1]=i
            else:

                b.pop(-1)
                I = b.index(tes)
                break
    d=len(b)-I
    e=(K-I+1+check)%d
    print(b[e-1])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False for _ in range(N)]

i = 1
c = 0
jun = []
while True:
    if i == A[i-1]:
        print(i)
        exit()
    if visited[i-1]:
        lp = i
        break
    else:
        visited[i - 1] = True
        jun.append(i)
        i = A[i-1]
        c += 1
ji = jun.index(lp)
K -= len(jun[:ji])
jun = jun[lp:]

kai = K % c

if kai == len(jun) + 1:
    print(jun[0])
else:
    print(jun[kai-1])

Submission status: Runtime Error

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy

def costCalc(index,cost):
    if cost < k:
        costCalc(a[index]-1,cost+1)
    else:
        print(index+1)


if __name__ == '__main__':
    n, k = map(int, input().split())
    sys.setrecursionlimit(k)
    a = [int(i) for i in input().split()]
    costList = [-1]*n
    costCalc(0,0)
    maxCount = max(costList)+1

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
global s
for i in range(k):
    key
    if(i==0):
        key=0
    s=a[key-1]
    if(i==k-1):
        break
    key=a[s-1]
print(s)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
lst = list(map(int, input().split()))
data = [-1]*n

k -= 1
tmp = lst[0]
for i in range(1, k+1):
  #print(tmp, "t")
  if data[lst[tmp-1]-1] >= 1:
    num = i - data[lst[tmp-1]-1]
    break
  else:
    data[tmp-1] = i
    tmp = lst[tmp-1]

for j in range((k-i)%num + 1):
  tmp = lst[tmp-1]
print(tmp)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
r = [0]*N
p = 0
q = 1 #現在地
for i in range(K):
    q = A[q-1] #次の町
    if r[q-1] == 0:
        p += 1
        r[q-1] += p       
    else:
        p += 1
        y = r[q-1]
        break
z = (K-y) % (p-y)
for i in range(N):
    if r[i] == y+z:
        print(i+1)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = list(map(int, input().split()))
B = [i for i in range(1, N+1)]
d = dict(zip(B, A))
t = [0 for i in range(N)]
d1 = dict(zip(B, t))
temp = 1
cnt = 0
ans = []
for i in range(K):
    d1[d[temp]] = d1.get(d[temp], 0)+1
    if d1.get(d[temp], 0) == 2:
        cnt += 1
        ans.append(d[temp])
        # print(i, d[temp])
    if d1.get(d[temp], 0) == 3:
        break
    temp = d[temp]
cnt1 = 0
for i, v in enumerate(d1):
    if v == 1:
        cnt1 += 1
# print(cnt, cnt1, d1, temp, ans)
k = K-1-cnt1
print(ans[k % cnt])

Submission status: Runtime Error

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input = sys.stdin.readline
    n,k=L()
    a=L()
    visited=[0]*n
    tmp=0
    now=0
    visited[0]=1
    
    for i in range(k):
        #print(visited,end="")
        now=a[now]-1
        #print(now)
        #print(tmp,now+1)
        if visited[now]==0:
            visited[now]=i+2
        else:
            tmp=i+2
            loopat=now
            break
    #print(visited)
    #print(loopat,visited[loopat],tmp)
    #print(tmp,now)
    tmp2=(k-(visited[loopat]-1))%(tmp-visited[loopat])
    #print(tmp2)
    dist=loopat+1
    #print(now,dist)
    #print(now+1,end=" ")
    for i in range(tmp2):
        now=a[now]-1
        dist=now+1
        #print(now,dist)
    #print()
    print(dist)
    
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
import numpy as np
setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = [0]+a
bunki = 0
now = a[1]
lip = [1]
while True:
    bunki += 1
    if now in lip:
        break
    lip.append(now)
    now = a[now]

tenki = lip.index(now)

lis = lip[tenki:]

roop = bunki-tenki

if k < tenki: 
    print(lip[k])
    exit()
k -= tenki

print(lis[k%roop])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
lst=list(map(int,input().split()))
ans=1
count=0
a=[]
a.append(1)
for i in range(k):
  ans=lst[ans-1]
  count+=1
  if ans in a:
    break
  else:
    a.append(ans)
k-=count
dif=count-a.index(ans)
for j in range(k%dif):
  ans=lst[ans-1]
print(ans)

Submission status: Runtime Error

Solution code:

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

loop = [0]
loop_corr = []
while len(loop) < k:
    curr = loop[len(loop) - 1]
    if a[curr] not in set(loop):
        loop.append(a[curr])
        # print(loop)
    else:
        loop_corr = loop[loop.index(a[curr]):len(loop)]
        break
        # loop_idx.append(loop.index(a[curr]))
        # loop_idx.append(len(loop)-1)


# print(loop)
# print(loop_corr)
if len(loop) > k:
    print(loop[k]+1)
else:
    diff = k - len(loop) + 1
    mod = (diff % len(loop_corr)) -1
    # print(diff)
    # print(mod)
    print(loop_corr[mod]+1)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = [int(x) - 1 for x in input().split()]

# 最初のループを回るまで
loop = 0
city = 0
b = set([0])
while True:
    loop += 1
    if A[city] in b:
        break
    else:
        city = A[city]
        b.add(city)

loop_start = A[city]

# ループの始点にたどり着くまで
pre = 0
city = 0
while True:
    pre += 1
    if A[city] == loop_start:
        break
    else:
        city = A[city]

if loop > pre:
    loop -= pre

if K < c:  # ループに入る前に終了の場合
    city = 0
    for i in range(K):
        city = A[city]
    print(city + 1)
    
else:  # ループに入って終了
    K -= pre
    last = K % loop
    city = loop_start
    
    for i in range(last):
        city = A[city]
    print(city + 1)

Submission status: Runtime Error

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, K = In.ints()
A = [0]+In.ints()

cur = 1
seen = set()
seen.add(cur)
circleStart = 0

i = 0
while i<K:
    cur = A[cur]

    if cur not in seen:
        seen.add(cur)
    else:
        circleStart = cur
        break
    i+=1

if i == K:
    Out.int(cur)
else:
    K-=i+1

    dist = dict()
    dist[0] = circleStart
    cur_dist = 0
    longest = 0

    i = 0
    while i<K:
        cur_dist+=1

        cur = A[cur]

        if cur!=circleStart:
            dist[cur_dist] = cur
            longest = max(cur_dist, longest)
        else:
            i+=1
            break

        i+=1

    if i == K:
        Out.int(cur)
    else:
        K-=i+1
        Out.int(dist[K%longest])


######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Runtime Error

Solution code:
n,k = (int(x) for x in input().split())
town = [int(i) for i in input().split()]
warp  = [1]
checklist = [0]+[-1]*n
i = 0
j = 0
while j<=n:
    warp.append(town[i])
    if checklist[town[i]-1]!=-1:
        s = checklist[town[i]-1]
        warp = warp[s:j]
        break
    checklist[town[i]-1] = j
    i = town[i]-1
    j += 1


m = len(warp)
print(warp[(k-s)%m])

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
loc=0
x=[-1]*N
y=0
distance=0
flag=False
for i in range(N+1):
  if(x[loc]>=0):
    distance=i-x[loc]
    y=x[loc]
    flag=True
    break
  else:
    x[loc]=i
  loc=A[loc]-1
if(flag==True and y+distance<K):
  print(x.index((K-y)%distance+y)+1)
else:
  print(x.index(K)+1)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())

a = list(map(int, input().split()))
nxt = a[0]

for i in range(k):
    nxt = a[nxt] - 1

ans = a[nxt]
print(ans)

Submission status: Runtime Error

Solution code:
n, k = [int(i) for i in input().split()]
towns = [int(i) for i in input().split()]
ind_ = 1
ts = []
roop_s = None
for i in range(15):
    ind_ = towns[ind_-1]
    if ind_ in ts:
        roop_s = ts.index(ind_)
        break
    else:
        ts.append(ind_)
init = len(ts[:roop_s])
roop_l = len(ts) - init
roop = ts[roop_s:]
print(roop[((k-init)%roop_l)-1])

Submission status: Runtime Error

Solution code:
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find = deque([0])
i = 0
count = 0
while a[i]-1 not in roop_find:
    roop_find.append(a[i]-1)
    i = a[i] - 1
    count += 1
b = roop_find.index(a[i]-1)
roop = list(roop_find)[b:count+1]

if k < b:
    print(roop_f[k]+1)
else:
    k-=b
    e = k % len(roop)
    print(roop[e]+1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 21:34:02 2020

@author: shinba
"""


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

a = list(map(int,input().split()))

data = [0]*n
data[0] = 1

li = [0]

while k > 0:
    b = a[li[-1]]-1
    if data[b] == 0:
        data[b] = 1
        li.append(b)
        k -= 1
    else:
        break

if k != 0:
    for i in range(len(li)-1,-1,-1):
        if li[i] == b:
            s = b
            break
    newli = li[b:]
    l = (k-1) % len(newli)
    print(li[l]+1)
else:
    print(li[-1]+1)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(lambda x:int(x)-1,input().split()))
lst=[0]
now=0
memo=0
town=[0]*n
town[0]=1
for i in range(k):
	now=a[now]
	if town[now]==1:
		memo=now
		break
	lst.append(now)
	town[now]=1
i=a.index(memo)
l=len(lst)
if memo!=0:
	lst=lst[i:]
print(lst[(k-l)%len(lst)]+1)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
s = set()
s.add(1)
former = []
latter = []
temp = [1]
cur = a[0]
buf = 0

while True:
    if cur not in s:
        s.add(cur)
        temp.append(cur)
        cur = a[cur-1]
    else:
        buf = temp.index(cur)
        former = temp[:buf]
        latter = temp[buf:]
        break

# print('buf:', buf)
# print('former:', former)
# print('latter:', latter)

if len(latter) == 0:
    mod = k % len(temp)
    print(temp[mod])
    exit()

if k <= len(former):
    print(former[k])
else:
    mod = k % len(latter)
    # print('mod:', mod)
    idx = mod - len(former)
    print(latter[idx])

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = [0]
for i in range(6):
    p = A[B[i]]
    B.append(p-1)
i = 1
while i <=7:
    if B[i] in  B[0:i-1]:
        c = B[i]
        break
    i += 1
j = 0
d = 0
while j <= 6:
    if B[j] == c and d > 0:
        e = j
        break
    if B[j] == c:
        d = j
    j +=1
if K <= e:
    print(B[K]+1)
else:
    f = (K-d) % (e-d)
    print(B[d+f]+1)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
trans_list = list(map(int,input().split()))
cycle = []
cycle.append(1)
temp = trans_list[0]
for i in range(n):
    cycle.append(temp)
    temp = trans_list[temp-1]
#first 为第一次
#second weidierci
#value 为重复的值
first=0
second = 0
for i in range(n):
    if cycle.count(cycle[i])==2:
        first = i
        break;
for i in range(first+1,len(cycle)):
    if cycle[i] == cycle[first]:
        second = i
        break
cycle_length = second-first
###cycle==0
if cycle_length==0:
    index = k
else:
    index = first + (k - first) % cycle_length
print(cycle[index])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	mati = [0 for i in range(N)]
	for i,val in enumerate(A):
		mati[i] = val-1

	tugi = 0
	gizi = {}
	gizi2 = {}
	saigo = inf
	ans = []
	cnts = 0
	flg = False
	for i in range(K):
		tugi = mati[tugi]
		if flg == False:
			cnts += 1
			if tugi in gizi:
				flg = True
				ans.append(saigo)
				ans.append(tugi)
				gizi2[saigo] = 1
				gizi2[tugi] = 1
			else:
				gizi[tugi] = 1
				saigo = tugi
		else:
			if tugi in gizi2:
				break
			else:
				ans.append(tugi)
				gizi2[tugi] = 1

	tmp = len(ans)
	cnts = cnts - len(ans)
	kotae = (K-cnts+1) % (tmp)

	#print(cnts)
	#print(kotae)
	#print(ans)
	print(ans[kotae]+1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
#import math
#=input()
#=int(input())
n,k=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

q = a[0]
l = []
for i in range(k-1):
    if q in l:
        w = l.index(q)
        break
    l += [q]
    q = a[q-1]
f = len(l[:w])
ll = l[w:]
g = len(ll)
r = (k - f) % g - 1
print(ll[r])

Submission status: Runtime Error

Solution code:
n,K=list(map(int,input().split()))
a = list(map(int,input().split()))
b = []
c = [0]*len(a)
I=0
check=0
k=0
for i in range(n):
    b.append(a[k])
    tes=a[k]
    k=a[k]-1
    if a[k]==1:
        b.append(1)
        check=-1
        break
    else:
        if c[a[k]-1]==0:
            c[a[k]-1]=i
        else:

            b.pop(-1)
            I = b.index(tes)
            break
d=len(b)-I
e=(K-I+1+check)%d
print(b)
print(b[e-1])

Submission status: Runtime Error

Solution code:
N,K = list(map(int,input().split()))

A = list(map(int,input().split()))
visited = [1]
visited_list = [0]*N
visited_list[0] = 1
k = 0
l = 0
kaburi = 1
def f(Ai):
    global k,l,visited,kaburi
    # print("Ai",Ai,k)
    if k == K:
        print(A[Ai])
    elif visited_list[Ai-1] == 1 :
        kaburi = Ai
        k += 1
        l = k
    else:
        visited.append(Ai)
        visited_list[Ai-1] = 1
        k += 1
        f(A[Ai-1])

f(A[0])
hazime = visited.index(kaburi)
b = visited[hazime:]
# print(b)
# print(l)
print(b[(K-hazime)%(l-hazime)])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

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

    count = 0
    now = 0
    visited = [now+1]
    set_v = set()
    set_v.add(now+1)
    l = -1
    while count < N:
        x = A[now]
        if x in set_v:
            l = visited.index(x)
            break
        else:
            count += 1
            visited.append(x)
            set_v.add(x)
            now = x-1
    r = count
    #print(l,r,visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
if len(l) >= k-1:
    print(l[k])
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
cities = {}
city = 1
for num in range(1, N+1):
    cities[num] = int(input())
while K:
    city = cities[city]
    K -= 1
print(city)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
r = [0]*N
p = 0
q = 1 #現在地
for i in range(min(K,N)):
    q = A[q-1] #次の町
    if r[q-1] == 0:
        p += 1
        r[q-1] += p       
    else:
        p += 1
        y = r[q-1]
        break
z = (K-y) % (p-y)
for i in range(N):
    if r[i] == y+z:
        print(i+1)

Submission status: Runtime Error

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

ans=[]
judge={}
j=0 #A進み
while A[j] not in judge.keys() or judge[A[j]]!=2:
    ans.append(A[j])
    if A[j] not in judge.keys():
        judge[A[j]]=0
    judge[A[j]]+=1
    j=A[j]-1

st=ans.index(A[j])
ans=ans[st:]
if st<K:
    K-=st
    l=len(ans)
    #print(ans)
    print(ans[K%l-1])
else:
    print(ans[st])

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
al = list(map(int, input().split())) 
x=0
now = 1
nl =[1]
for i in range(0,k):
    now = al[now-1]
    nl.append(now)
    if len(nl) != len(set(nl)):
        loops = nl.index(now)
        loope = i+1
        break
    elif i==k:
        print(now)
        exit()

k = (k-loops) % (loope-loops) +loops
now =1
for i in range(0,k):
    now = al[now-1]
    nl.append(now)

print(now)

Submission status: Runtime Error

Solution code:
n,k = map(int, input().split())
list1 = list(map(int, input().split()))
list2 = []
now = 0
shuuki = 0
while k >= 1:
    if now not in list2:
        list2.append(now)
        now = list1[now] - 1
        k = k - 1
    else:
        shuuki = len(list2) - list2.index(now)
        break
k = k % shuuki
while k >= 1:
    now = list1[now] - 1
    k = k - 1
print(now + 1)

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A -= 1

flg = [False for _ in range(N)]
loop = 0
town = []
i = 0
while flg[i] == False:
    town.append(i)
    flg[i] = True
    i = A[i]
    loop += 1
else:
    loop_start = i

print(town[K % loop + loop_start] + 1)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
import sys

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

now = 1
record = [now]
rem = K
for k in range(K):
  if A[now-1] in record:
    record.append(A[now-1])
    break
  now = A[now-1]
  record.append(now)
  rem -= 1
record = np.array(record)
roop = record[np.where(record==record[-1])[0][0]:]
amari = rem % len(record)
print(roop[amari-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	mati = [0 for i in range(N)]
	for i,val in enumerate(A):
		mati[i] = val-1

	tugi = 0
	gizi = {}
	saigo = inf
	ans = []
	cnts = 0
	flg = False
	for i in range(K):
		tugi = mati[tugi]
		if flg == False:
			cnts += 1
			if tugi in gizi:
				flg = True
				ans.append(saigo)
				ans.append(tugi)
			else:
				gizi[tugi] = 1
				saigo = tugi
		else:
			if tugi in ans:
				break
			else:
				ans.append(tugi)

	tmp = len(ans)
	cnts = cnts - len(ans)
	kotae = (K-cnts+1) % (tmp)

	#print(cnts)
	#print(kotae)
	#print(ans)
	print(ans[kotae]+1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()