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()))
A=list(map(lambda x:x-1,A))

next=0
hoge=[]
for i in range(k):
    next=A[next]
    if next in hoge:
        t=next
        break
    else:
        hoge.append(next)

for i in range(len(hoge)):
    if hoge[i]==t:
        hoge_1=hoge[:i]
        hoge_2=hoge[i:]

if k<=len(hoge_1):
    ans = 0
    for i in range(k):
        ans=A[ans]
else:
    k=k-len(hoge_1)-1
    k=k%len(hoge_2)
    ans=hoge_2[0]
    for i in range(k):
        ans=A[ans]


print(ans+1)

Submission status: Runtime Error

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, K = LI()
A = LI()

tel = [-1] * N

i = 0
time = 1
while True:
    # print(i, end=" ")
    if time == K:
        print(A[i])
        break
    
    if tel[i] == -1:
        tel[i] = [time, A[i]-1]
        i = A[i]-1
    else:
        # i = A[i]-1
        break
    
    time += 1
    # print(time, tel)
# print()
# print(time-1)
# print(time - tel[i][0])
# print((K - (time-1)) % (time - tel[i][0]))

for _ in range((K - (time-1)) % (time - tel[i][0])):
    i = A[i]-1

print(i+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
already_town =[1]
now_town=1
count = 0
for i in range(K):
    already_town.append(A[now_town-1])
    now_town = A[now_town-1]
    count =i+1
    if(len(set(already_town))!=len(already_town)):
        break
beark_len=len(already_town)-1
cicle_start=already_town.index(already_town[-1])

print(already_town[(K)%(count-already_town.index(already_town[-1]))])

Submission status: Runtime Error

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

  
test = 1
find_f = {}
for i in range(N):
  find_f[i+1]=[]

find_f[1].append(0)
for i in range(K):
  test = move_list[test-1]
  find_f[test].append(i+1)
  if len(find_f[test]) == 2:
    state ,f = test, find_f[test]
    break
  
K = K-f[0]
f = f[1]-f[0]
remain = K%f

for i in range(remain):
  state = move_list[state-1]
  
print(state)
#state = 1

#for i in range(K):
#  state = move_list[state][1]

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = 0
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = []
    next = a[0]
    b.append(next)
    e = 0
    s = 0
    for i in range(n-1):
        next = a[next-1]
        if next in b:
            e = i
            s = b.index(next)
            break
        b.append(next)
    if k > e:
        ans = (k - s)%e
    else:
        ans = k%e
    print(b[ans])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    dict[i]=a[i]-1 #i番目の町からどこにつくか
tmp=0#現在知
num2city={}
city2num={}
city2num[0]=0#どのまちが何回目か
num2city[0]=0#j回目にどこにいるか
for j in range(k):
    tmp=dict[tmp]#現在地更新
    if tmp not in num2city.values():#現在地がまだきたことない
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j-1
        r=res%term
        #print(mae,term,res,r)
        temp=num2city[mae+r]
        break
  #  print(tmp+1)
    

print(tmp+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
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+len(lst)-l)%len(lst)]+1)
else:
	print(now+1)

Submission status: Runtime Error

Solution code:


def solve():
    hm = {}
    steps = k
    curr = 0
    loopsize = 0
    pre = 0
    while not str(curr) in hm and steps > 0:
        hm[str(curr)] = pre
        pre+=1
        curr = a[curr] - 1
        steps -= 1
        loopsize += 1
    loopsize -= hm[str(curr)]
    steps %= loopsize
    while steps > 0:
        curr = a[curr] - 1
        steps -= 1
    print(curr + 1)
    return



n, k = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
solve()

Submission status: Runtime Error

Solution code:
N, K= [int(i) for i in input().split()]
An = [int(i) for i in input().split()]

i = 0
checked = [0 for _ in range(N)]
c = 0
while checked[i] == 0:
  c += 1
  checked[i] = c
  i = An[i] - 1
if checked[i] >= K:
  i = 0
  for k in range(mod_K):
    i = An[i] - 1
  print(i + 1)
else:
  period = c - checked[i] + 1
  diff = K - checked[i] + 1
  mod_diff = diff % period
  for k in range(mod_diff):
    i = An[i] - 1
  print(i + 1)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
loop = [0]
dic = {0:0}

for i in range(K):
    if A[loop[-1]]-1 not in loop:
        dic[A[loop[-1]]-1] = i+1
        loop.append(A[loop[-1]]-1)
    else:
        idx = dic[A[loop[-1]]-1]
        break

l = len(loop)
print(loop[(K+1-idx)%(l-idx)+idx-1]+1)

Submission status: Runtime Error

Solution code:
temp = input().split(" ")
n = int(temp[0])
k = int(temp[1])

temp = input().split(" ")
telep = [int(i) for i in temp]

#n = 7
#k = 20

#telop = [2, 3, 4, 5, 6, 7, 3]
alreadyVisited = []

now = 1
piv = -1
counter = 0

for i in range(k):
    alreadyVisited.append(now)
    now = telep[now - 1]
    if now in alreadyVisited:
        piv = now
        break
    else:
        counter += 1
        pass
    
#print(counter)
#print(alreadyVisited)

#print(piv)
index = alreadyVisited.index(piv)
nl = alreadyVisited[index:]

#print(nl)

looptime = len(nl)
beforeloop = index

#print(beforeloop)
#print(looptime)

hoge = k - beforeloop
#print(hoge)

#print(divmod(hoge, looptime))

_, h2 = divmod(hoge, looptime)
#print(h2)

print(nl[h2])

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    n,k = map(int,stdin.readline().rstrip().split())
    As = list(map(int,stdin.readline().rstrip().split()))
    As = [0]+As
    g = set({1})
    l = [0,1]
    now = 1
    for i in range(1,k+1):
        now = As[now]
        if now in g:
            break
            
        else:
            g.add(now)
            l.append(now)

    j = l.index(now)
    print(l[j+(k-i)%(i+1-j)])
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.insert(0, 0)
r = 1
now = a[1]
b = [1]
chk = [0] * (n + 1)
chk[1] = 1
kk = k - 1

while chk[now] == 0:
    chk[now] = 1
    b.append(now)
    now = a[now]
    kk -= 1

if now == 1:
    c = b
else:
    c = b[now:]
    
if k <= len(b):
    print(b[k - 1])
else:
    print(c[kk % len(c)])

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, sys.stdin.readline().strip().split())
A = list(map(int, sys.stdin.readline().strip().split()))

town_line = []
town_set = set()
last_town = None


def search(town=0):
    global last_town
    if town not in town_set:
        town_line.append(town)
        town_set.add(town)
        search(town=A[town]-1)
    else:
        last_town = town
        return


search(0)
town_loop = town_line[town_line.index(last_town):]

if K < len(town_line):
    print(town_line[K] + 1)
else:
    k = K - len(town_line) + 1
    k = k % len(town_loop)
    print(town_loop[k - 1] + 1)

Submission status: Runtime Error

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

MyList = [int(n) for n in MyList]

ANS = 0
visted = []

def Myfunc(A):
    return MyList[A] - 1

for i in range(K):
    if ANS in visted:
        beANS = K % (len(visted)-1)
        ANS = visted[beANS-1]
        print(ANS+1)
        break
    else:
        ANS = Myfunc(ANS)
        visted.append(ANS)
    if i +1 == K:
        print(ANS+1)

Submission status: Runtime Error

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

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

reach = [-1 for i in range(N)]
reach[0] = 0 #最初の町は0回でいく
now = 0
#loop = 1
dic ={}
dic[0] = 0
for i in range(N):
  to = A[now]-1
  if reach[to] != -1:
    ini = i+1
    #print(i,to,reach[to])
    loop = i+1 - reach[to]
    break
  if i+1 not in dic:
    dic[i+1] = to
  reach[to] = i+1
  #loop += 1
  now = to


#print(dic,reach,loop,ini)
if K <= ini:
  print(dic[K]+1)
else:
  t = (ini-loop) + (K-ini)%loop
  print(dic[t]+1)

Submission status: Runtime Error

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

tele=[0]*N
for i in range(N):
    tele[i]=list[i]-1

temp=[0]*100
town=0
for i in range(100):
    temp[i]=tele[town]
    town=tele[town]

for i in range(100):
    for j in range(100):
        if temp[i]-temp[j]==0:
            mod=abs(i-j)
            break
K_temp=K%mod

city=0
for i in range(K_temp):
    city=tele[city]

print(city+1)

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]
    L=[1]
    a = A[0]
    for _ in range(N-1):
        L.append(a)
        a=A[a-1]
        if a==1:
            g=K%len(L)
            print(l[g])
            break
        elif a in L:
            x = L.index(a)
            g = (K-x )%(len(L)-x)
            print(L[x:][g])
            break
    
main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
passlist = [0]*N
point = 1
depth = 0
waylist = []
while passlist[point-1] == 0:
    passlist[point-1] = 1
    point = A[point-1]
    waylist.append(point)
    depth+=1
print(waylist[depth-K%depth])

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
DP=[[0,0] for i in range(N)]

visited=[0]*N#訪問フラグ
ima_pos=0#現在地
mirai_pos=0#移動先

count_first=0#一巡目のループ
first_DP=[]
count_second=0#2巡目以降のループ
second_DP=[]

while(visited[ima_pos]==0):
  visited[ima_pos]=1#訪れたら更新
  mirai_pos=A[ima_pos]-1
  ima_pos=mirai_pos
  first_DP.append(ima_pos)
  count_first+=1#何回移動したか

second_start=ima_pos#2巡目ループのスタート地点

while(True):#スタート地点に戻ってきたら抜ける
  visited[ima_pos]=2#訪れたら更新
  mirai_pos=A[ima_pos]-1
  ima_pos=mirai_pos
  second_DP.append(ima_pos)
  count_second+=1#何回移動したか
  if ima_pos==second_start:
    break

if K<=len(first_DP):
  print(first_DP[K]+1)
else:
  cc=K-len(first_DP)
  print(second_DP[ cc%len(second_DP)-1 ]+1)

Submission status: Runtime Error

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

pos = -1
seen = [False] * n
finished = [False] * n
hist = []
cycle = []
cycles = [-1] * n
cn = {}

def dfs(v, p):
    global pos
    seen[v] = True
    hist.insert(0, v)
    next = a[v]-1
    if (next != p):
        if (finished[next] == False):
            if (seen[next]):
                pos = next
                return
            dfs(next, v)
            if (pos != -1):
                return

    hist.pop(0)
    finished[v] = True

dfs(0, -1)
cnt = 0
while(len(hist) != 0):
    b = hist[0]
    cycle.append(b)
    cycles[b] = cnt
    cn[b] = cnt
    cnt += 1
    hist.pop(0)
    if (b == pos):
        break
cycle = list(reversed(cycle))

n = 0
ans = -1
while(cycles[n] == -1 and k > 0):
    k -= 1
    n = a[n] - 1
    if(k == 0):
        ans = n

if (k > 0):
    dc = len(cycle) - cn[n] - 1
    d = (k+dc) % len(cycle)
    ans = cycle[d] + 1

print(ans)

Submission status: Runtime Error

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

X = 0
town = 1
counted = []
for k in range(N):
  X += 1
  counted.append(town)
  town = A[town-1]
  if town in counted:
    Q = len(counted[counted.index(town):])
    roop = counted[counted.index(town):]
    I = counted[:counted.index(town)]
    ini = X - Q
    break
print(I)
print(roop)
ans = 1
if K > ini:    
  num = (K-ini) % Q
  print(roop[num])
else:
  print(I[K])

Submission status: Runtime Error

Solution code:
from _collections import deque

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

r = deque(['1'])

fhinish_roop = 0
index = 0
while not fhinish_roop:
    if str(a[index]) not in r:
        r.append(str(a[index]))
        index = a[index] - 1
    else:
        fhinish_roop = 1
        r_2 = "".join(r)
# print(r, index)
roop_l = r_2.find(str(a[index]))
# print(roop_l)
roop_len = len(r) - roop_l
roop_start_index = roop_l
# print(roop_len)

if k < roop_start_index:
    print(a[k - 1])

else:
    ans = (k - roop_start_index) % roop_len
    # print('ans={}'.format(ans))
    print(r[roop_start_index + ans])

Submission status: Runtime Error

Solution code:
n, k = [int(i) for i in input().split()]
al = [int(i) for i in input().split()]

index = 0
keiro = []
s_keiro = set()

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    break
  s_keiro.add(index)
  keiro.append(index)

pos = (k-start) % mod
print(keiro[start + pos - 1]+1)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
dist = [[] for i in range(N)]
A = list(map(int, input().split()))
for i in range(N):
    dist[i].append(A[i] - 1)
dp = [[0, 0] for i in range(N)]

def dfs(pos, depth):
    # 初めての訪問なら
    if dp[pos][0] == 0:
        dp[pos][0] = depth
        for i in dist[pos]:
            dfs(i, depth + 1)
    elif dp[pos][1] == 0:
        dp[pos][1] = depth
        for i in dist[pos]:
            dfs(i, depth + 1)
dfs(0, 0)
for i in range(N):
    split = dp[i][1] - dp[i][0]
    if split != 0:
        if (K - dp[i][0]) % split == 0:
            print(i + 1)
            break

Submission status: Runtime Error

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

li = [0]
li.extend(list(map(int, input().split())))

def search(town, li, times):
  if times == 0:
    return town
  return search(li[town], li, times-1)

tuita = [0]*(n+2)
cnt = 0
town = 1
while True:
  town = li[town]
  cnt += 1
  if tuita[town] == 0:
    tuita[town] = cnt
  else:
    if k < tuita[town]:
      print(search(1, li, k))
    elif k == tuita[town]:
      print(town)
    else:
      print(search(town, li, (k - tuita[town]) % (cnt - tuita[town])))
    break

Submission status: Runtime Error

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

l = [-1] * N
loopcnt = 0
inicnt = 0
place = 1
i = 0
l[place - 1] = 0

while i <= K:
    i += 1
    next_place = A_list[place - 1]
    place = next_place
    if l[next_place - 1] != -1:
        loopcnt = i - l[next_place - 1]
        inicnt = l[next_place - 1]
        break
    else:
        l[next_place - 1] = i

last_move_cnt = (K - inicnt) % loopcnt

j = 1
while j <= last_move_cnt:
    j += 1
    next_place = A_list[place - 1]
    place = next_place
    
print(place)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    ans = 0
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = []
    next = a[0]
    b.append(next)
    e = 0
    s = 0
    for i in range(n-1):
        next = a[next-1]
        if next in b:
            e = i
            s = b.index(next)
            break
        b.append(next)
    if k > e:
        ans = (k - s)%e
    else:
        ans = k%e
    print(b[ans])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve(n, k, a_list):
    a_visit = [False] * (max(a_list) + 1)
    loop_list = []
    next_visit = a_list[0]
    while True:
        # print('next_visit', next_visit)
        if not a_visit[next_visit]:
            loop_list.append(next_visit)
            a_visit[next_visit] = True
            next_visit = a_list[next_visit - 1]
        else:
            break
    # print(loop_list, a_visit)
    if 1 in loop_list:
        position = (k) % len(loop_list)
    else:
        position = (k - 1) % len(loop_list)
    # print(position, loop_list[position-1])
    return loop_list[position-1]



def main():
    n, k, a_list = input_from_console()
    print(solve(n, k, a_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Runtime Error

Solution code:
"""
"""
N, K = map(int, input().split())
A = list(map(int, input().split()))
loop_end_list = {1}
loop = 0
while True:
    s = A[0]
    e = A[s-1]
    if e in loop_end_list:
        break
    else:
        loop_end_list.append(e)
        loop += 1
ans = K % loop
if ans == 0:
    print(1)
else:
    print(loop_end_list[loop])

Submission status: Runtime Error

Solution code:
from itertools import combinations
import numpy as np
N, M, X = map(int,input().split())
xx = np.array([X]*M)
C = {}
cs = []
for _ in range(N):
    c, *A = map(int,input().split())
    C[c] = A
    cs.append(c)
ans = float('inf')
for i in range(0, N+1):
    for comb in combinations(cs,i):
        tmp = 0
        x = xx.copy()
        for cos in comb:
            tmp += cos
            x -= np.array(C[cos])
        if len(x[x <= 0]) >= M:ans = min(ans,tmp)
if ans == float('inf'):ans = '-1'
print(ans)

Submission status: Runtime Error

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

A = list(map(int, input().split())) 
B = []

i = 1
now = A[0] - 1
B.append(0)
while i <= K:
    if now in B:
        s = B.index(now)
        t = (K - s) % (len(B) - s)
        break
    B.append(now)
    now = A[now] - 1
    i += 1
 
print(B[s + t] + 1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
li = list(map(int,input().split()))
count = 2
li2 = [1]
li2.append(li[0])
for i in range(k):
    li2.append(li[li2[i+1]-1])
    count += 1
    if len(set(li2)) != count:
        break
s = li2.index(li2[-1])
del li2[0:s]
del li2[-1]
print(li2[(k-s) % len(li2)])

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
visited = {'1': 0}
route = [1]
next_id = 0
count = 0
while count < K:
    count += 1
    if A[next_id] in visited.keys():
        break
    visited[A[next_id]] = count
    route.append(A[next_id])
    next_id = A[next_id] - 1
roop = route[visited[A[next_id]]:]
print(roop[(K - count) % len(roop)])

Submission status: Runtime Error

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

tele=[0]*N
for i in range(N):
    tele[i]=list[i]-1

temp=[0]*6
town=0
for i in range(6):
    temp[i]=tele[town]
    town=tele[town]

for i in range(6):
    for j in range(6):
        if temp[i]-temp[j]==0:
            mod=abs(i-j)
            break
K_temp=K%mod

city=0
for i in range(K_temp):
    city=tele[city]

print(city+1)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=1
t=0
path=[]
s=set()
cycle=[]
while(c<=k):
    c+=1
    if a[t] in s:
        #print(path.index(a[t]),a[t])
        cycle=path[path.index(a[t]):]
        k-=c-1
        break
    path.append(a[t])
    s.add(a[t])
    t=a[t]-1
    #print(path,c)
#print(cycle)
print(cycle[k%len(cycle)])

Submission status: Runtime Error

Solution code:
# D

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

def compute(city, K):
    for i in range(K):
        # print('\t', city)
        city = As[city-1]
    print(city)


if N > K:
    compute(1, K)

cities_visited = [False] * N
i = 0
city = 1
city_visited_time = {}

while not cities_visited[city - 1]:
    # print(city)
    cities_visited[city - 1] = True
    city_visited_time[city-1] = i
    city = As[city-1]
    i += 1

loop_start = city_visited_time[city-1]
loop_end = i

if loop_end - loop_start == 1:
    return city
div = (K - loop_start) // (loop_end - loop_start + 1)
# print(loop_start, loop_end, div, K % (loop_end - loop_start + 1))
compute(city, K % (loop_end - loop_start + 1) + loop_start + 1)

Submission status: Runtime Error

Solution code:
def main():
    n, k, *a = map(int, open(0).read().split())
    a = [0] + a
    root = [1]
    start = a[1]
    root.append(start)
    now = start
    roop = 0
    while True:
        next = a[now]
        if next in root:
            roop = next
            break
        else:
            root.append(next)
            now = next

    if roop == 0:
        ans = root[k]
    else:
        roop_start = root.index(roop)
        step = roop_start + 1
        if k <= step:
            ans = ans[k]
        else:
            m = len(root) - roop_start
            p, q = divmod(k - step + 1, m)
            index = roop_start + q
            ans = root[index]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# N = int(input())

import numpy as np

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

visited = set()
from2to = {}
for i,a in enumerate(As):
    from2to[i+1] = a

id2n_warp = {}
current = 1
loop_anchor = -1
n_warp = 0
visited.add(1)
id2n_warp[1] = 0
while True:
    n_warp += 1
    next_ = from2to[current]
    if n_warp == K:
        print(next_)
        exit()
    if next_ in visited:
        loop_anchor = next_
        break
    else:
        id2n_warp[n_warp] = next_
        visited.add(next_)
    current = next_

K -= id2n_warp[loop_anchor]
# print(n_warp)
# print(K)
# print(id2n_warp[loop_anchor])
K = K % (n_warp - id2n_warp[loop_anchor]) if n_warp - id2n_warp[loop_anchor] > 0 else K

current = loop_anchor
for i in range(K):
    next_ = from2to[current]
    current = next_

print(next_)

Submission status: Runtime Error

Solution code:
while True:
    k -= 1
    cnt += 1
    if k == 0:
        break
    dir = a[dir - 1]
    if hash_a[dir - 1] == 0 or hash_a[dir - 1] == 1 or hash_a[dir - 1] == 2:
        hash_a[dir - 1] += 1
        if hash_a[dir - 1] == 2:
            two += 1
    elif hash_a[dir - 1] == 3:
        k = (k + cnt) - (cnt - (two * 2))
        k %= two
        hash_a = [-k for _ in range(n)]
print(dir)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(len(a)):
  a[i]-=1
l = [0]
jud = 0
f = 0
for i in range(n):
  m = a[l[-1]]
  if(m in l):
    jud = 1
    f = m
    break
  l.append(m)
p = n
ll=len(l)
if(jud==1):
  for i in range(ll):
    if(l[i] != m):
      del l[0]
      k-=1
    else:
      p = len(l)
      break
print(a[k%p]+1)

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
a = list(map(int, input().split()))
ans = a[0]
check = []
for i in range(K):
    check.append(ans)
    ans = a[ans-1]
    if len(set(check)) != len(check):
        tmp = i
        tmp_s = check.index(check[i])
        break
#print(tmp_s)
#print(tmp)
#print(check)
ans = a[0]
for j in range((K- tmp_s+1)%tmp +1):
    ans = a[ans-1]
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
B=[1]
i=0
for i in range(K):

    B.append(A.index(B[i])+1)

    if(len(set(B))!=i+2):

        blast=B[-1]
        bfirst=B.index(blast)
        roop=len(B)-bfirst
        ans=(K-bfirst)%roop
        print(B[ans])
        exit()

Submission status: Runtime Error

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

dist = A[0]
visited = {1}
_v = [1]
stop = 0
while True:
    if dist in visited:
        stop = dist
        break
    visited.add(dist)
    _v.append(dist)
    dist = A[dist-1]

made = 0
for i in range(len(_v)):
    if _v[i] == stop:
        break
    made += 1

loop = len(_v) - made
_v = _v[made:]

# print(stop)
# print(loop)
# print(made)
# print(_v)

if K <= made:
    print(_v[K])
else:
    K -= made
    K %= loop
    print(_v[K])

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(K):
  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:
# -*- 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()

	if N == 1:
		print(1)
		sys.exit()

	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:
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(K):
  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())
dist = [[] for i in range(N)]
A = list(map(int, input().split()))
for i in range(N):
    dist[i].append(A[i] - 1)
dp = [[0, 0] for i in range(N)]

def dfs(pos, depth):
    # 初めての訪問なら
    if dp[pos][0] == 0:
        dp[pos][0] = depth
        for i in dist[pos]:
            dfs(i, depth + 1)
    elif dp[pos][1] == 0:
        dp[pos][1] = depth
        for i in dist[pos]:
            dfs(i, depth + 1)
dfs(0, 0)
for i in range(N):
    split = dp[i][1] - dp[i][0]
    if split != 0:
        if (K - dp[i][0]) % split == 0:
            print(i + 1)
            exit()