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: Time Limit Exceeded

Solution code:
from collections import deque

N, K = map(int, input().split())
tele = list(input().split())
seen = deque([])
now = 1
w_num = 0

while now not in seen and w_num < K:
    seen.append(now)
    now = int(tele[now - 1])
    w_num += 1
    
if w_num == K:
    print(now)
else:
    roop_in_index = seen.index(now)
    roop = list(seen)[roop_in_index:]
    roop_len = len(roop)
    last = (K - (w_num - 1)) % roop_len
    print(roop[last - 1])

Submission status: Time Limit Exceeded

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


def main() -> None:
    N, K = rmi()
    A = rmi()
    route = {}
    road = [1]
    current = 1
    # route map make
    for n in range(N):
        if not current in route:
            route[current] = A[current - 1]
            road.append(A[current - 1])
            current = A[current - 1]
        else:
            break
    # route map check
    dup = [x for x in set(road) if road.count(x) > 1][0]
    if dup == 1:
        loop = road[:-1]
        rem = K % len(loop)
        w(loop[rem])
    else:
        indexes = [i for i, x in enumerate(road) if x == dup]
        loop = road[indexes[0]: indexes[1]]
        if K < indexes[0]:
            w(road[K])
        else:
            K -= indexes[0]
            rem = K % len(loop)
            w(loop[rem])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Time Limit Exceeded

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

now = A[0]

for i in range(K-1):
    now = A[now-1]
    
print(now)

Submission status: Time Limit Exceeded

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

l = [1]

now_town = 1
loop_town = 0
for i in range(N):
    now_town = A[now_town-1]
    if now_town in l:
        loop_town = l.index(now_town)
        break
    else:
        l.append(now_town)

loop_num = len(l)-loop_town
if K > loop_town:
    num = (K - loop_town)%loop_num + loop_town
else:
    num = K
# 
# num = (K+1)%len(l)
# print(l)

print(l[num])

Submission status: Time Limit Exceeded

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

l=[1]
for i in range(k):
    x=a[l[i]-1]
    if x in l:
        break
    else:
        l.append(x)

b=l.index(x)
c=len(l)-b
print(l[((k-b)%c)+b])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
a = [0] + a

rep_check = 0
now = 1
place = []

if now == a[1]:
    print(1)
    exit()

while now not in place:
    place.append(now)
    now = a[now]
    rep_check += 1
    if rep_check == k:
        print(now)
        exit()

rep_start = 0
for i in enumerate(place):
    if i[1] == now:
        rep_start = i[0]
        break

k -= rep_start
rep_cnt = len(place) - rep_start

place = place[rep_start:]
k %= rep_cnt
print(place[k])

Submission status: Time Limit Exceeded

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

print(d)

Submission status: Time Limit Exceeded

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
route = [1]
dest = A[0]
while dest not in route:
    route.append(dest)
    dest = A[dest - 1]
ind = route.index(dest)
cycle = route[ind:]
if k >= ind:
    ans = (k - ind) % len(cycle)
    print(cycle[ans])
else:
    print(route[k])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque

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

L=[]
chk=[0 for _ in range(N)]
tmp=0
while(1):
    if chk[tmp]==1:
        break
    chk[tmp]=1
    L.append(tmp)
    tmp=A[tmp]-1

loop_s=A[L[-1]-1]-1
loop_g=L[-1]-1
one_to_s=0
tmp=0
while(1):
    if tmp==loop_s:
        break
    tmp=A[tmp]-1
    one_to_s+=1

loop_l=0
tmp=loop_s
Loop=[loop_s]
while(1):
    if tmp==loop_g:
        break
    tmp=A[tmp]-1
    Loop.append(tmp)
    loop_l+=1
loop_l+=1

if K<=one_to_s:
    tmp=0
    cnt=0
    while(1):
        if cnt==K:
            break
        tmp=A[tmp]-1
        cnt+=1
    ans=tmp + 1
else:
    K-=one_to_s
    num=K%loop_l
    ans=Loop[num]+1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(K):
  if i==0:
    now = A[0]
    
  else:
    now = A[now-1]
    
print(now)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A =[0]+list(map(int,input().split()))
l= 1
a = A[1]
B = [1]

while a != 1:
  B.append(a)
  a = A[a]
  l += 1

m = k % l
print(B[m])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
kosuu = 1
tadoru = [1]
pin = 1
tmp = 1
while pin == 1:
    tmp = A[tmp-1]
    if tmp == 1:
        break
    else:
        tadoru.append(tmp)
        kosuu += 1
mod = K % kosuu
print(tadoru[mod])

Submission status: Time Limit Exceeded

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

num_list = [1]
flag = True
while flag:
    tmp = a_list[num_list[-1]-1]
    if tmp in num_list:
        flag = False
    else:
        num_list.append(tmp)
        
idx = num_list.index(tmp)
loop = len(num_list) - idx
if k < idx:
    print(num_list[k])
else:
    print(num_list[(k-idx)%loop  + idx])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
    if next_machi in machi_list:
        break
    count += 1
    machi_list.append(next_machi)
    machi = next_machi
    next_machi = x[machi] - 1

z = 0
for i in range(0, count):
    if machi_list[i] == next_machi:
        z = i
        break
loop_machi_list = machi_list[z:]
if k < z:
    machi = machi_list[k] + 1
    print(machi)
else:
    k = k - z
    machi = loop_machi_list[k % len(loop_machi_list)] + 1
    print(machi)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
towns = [1]
prev = 1
count = 0
while len(towns) == len(set(towns)):
    next = a[prev - 1]
    towns.append(next)
    prev = next
    count += 1
    if count == k:
        print(next)
        sys.exit()
i = towns.index(next)
repeat = towns[i: -1]
unit = len(repeat)
rest = k - count + 1
print(repeat[(rest % unit) - 1])

Submission status: Time Limit Exceeded

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

dic = {}
for i in range(1, n+1):
    dic[i] = A[i-1]

L = [1]
tmp = 1
ct = 0
check = 0
while True:
    x = dic[tmp]
    ct += 1
    if x in L:
        check = x
        break
    else:
        L.append(x)
        tmp = x
p = L.index(check)
l = len(L)
roop = l - p
if k < p:
    print(L[k])
else:
    k -= p
    k %= roop
    print(L[p + k])

Submission status: Time Limit Exceeded

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

actual_position = position + 1
print(actual_position)

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k=map(int,input().split())
a=[int(x) for x in input().split()]
vis=[0]
now=0
for i in range(1,k+1):
  now=a[now]-1
  if now in vis:
    bgn=vis.index(now)
    print(vis[bgn+((k-bgn)%(len(vis)-bgn))]+1)
    sys.exit()
  else:
    vis.append(now)
print(vis[-1]+1)

Submission status: Time Limit Exceeded

Solution code:
def ma():
    return map(int,input().split())
y="Yes"
t="No"
n,k=ma()
A=list(ma())
ans=[]
now=1
while True:
    ans.append(now)
    now=A[now-1]
    if now in ans:
        use=ans.index(now)
        tool=len(ans)-use
        break 

if use>=k:
    print(ans[k])
    exit()
else:
    p=(k-use)%tool
    print(ans[use+p])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(n) for n in input().split()]
i = 1
dest = 1
while i < K:
    i += 1
    dest = A[dest-1]
print(A[dest-1])

Submission status: Time Limit Exceeded

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

T = [0] * (n + 1)
T[0] = 1

for i in range(1, n + 1):
    if A[T[i - 1] - 1] in T:
        last = i
        break
    else:
        T[i] = A[T[i - 1] - 1]

start = T.index(A[T[last - 1] - 1])

if k <= last:
    print(T[k])
else:
    print(T[start + (k - start) % (last - start)])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split());
data = [input().split()];
a = 1;
dest = int(1);

while a <= k:
    y = dest - 1;
    dest = int(data[0][y]);
    a = a + 1;
    
    
print(dest);

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = input_to_int_tuple()

    place = 1
    place_goned = [place]
    i = 0
    while i < n:
        place = a[place - 1]
        if place in place_goned:
            break

        place_goned.append(place)
        i += 1

    if k < len(place_goned):
        return place_goned[k]

    pre_loop_cnt = place_goned.index(place)
    move_cnt = k - pre_loop_cnt
    return place_goned[pre_loop_cnt:][move_cnt % len(place_goned[pre_loop_cnt:])]


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

root = [1]

for i in range(n):
    t = a[root[i] - 1]
    root.append(t)
    if (t in root[:-1]):
        break
x =  root.index(root[-1])
bef = root[0:x]
#print(bef)
loop = root[x:-1]
#print(loop)
#print(root)

if (k < len(bef)):
    print(bef[k])
else:
    p = ((k - len(bef)) % len(loop))
    #print(p)
    print(loop[p])

Submission status: Time Limit Exceeded

Solution code:
#2020-05-10
n, k = map(int,input().split())
lst = list(map(int,input().split()))
ans = 1
for i in range(k):
    ans = lst[ans - 1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
li = list(map(int, input().split()))
i = 0
t = 1
while i < k:
    t = li[t-1]
    i += 1
print(t)

Submission status: Time Limit Exceeded

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

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

C = [1]
i = 0

while True:
    C.append(A[i])
    i = A[i]-1
    if i == 0:
        C.pop(len(C)-1)
        break
        
r = K % len(C)


print(C[r])

Submission status: Time Limit Exceeded

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

Pos = 1
for i in range(K):
    Pos = Dst[Pos - 1]
print(Pos)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
li = list(map(int,input().split()))
ans = [1]

for i in range(n):
    now = ans[-1]
    nex = li[now-1]
    if ans.count(nex) > 0: #循環判定
        a = ans.index(nex) #開始点
        b = ans.index(now)-a+1 #循環周期
        break
    ans.append(li[now-1])

if k <= a:
    print(ans[k])
else:
    x = (k-a)%b
    print(ans[a+x])

Submission status: Time Limit Exceeded

Solution code:
import sys

N, K = map(int, sys.stdin.readline().rstrip().split())
A = list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

p = 0
moved = [p]
for i in range(K):
    next_p = A[p]
    if next_p in moved:
        start = moved.index(next_p)
        loop = moved[start:]
        remain = K - i - 1
        print(loop[remain % len(loop)] + 1)
        sys.exit()
    moved.append(next_p)
    p = next_p

print(p + 1)

Submission status: Time Limit Exceeded

Solution code:
towns = {}
n,k = list(map(int , input().split(' ') ))
ar = list(map(int,input().split(' '))) 
for i in range(1, n+1):
  towns[i] = ar[i-1]
temp = 1
while k:
  temp = towns[temp]
  k -=1
print(temp)

Submission status: Time Limit Exceeded

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

for _ in range(min(k, n)):
    nx = a[c[-1]-1]
    if not nx in c:
        c.append(nx)
    else:    
        cs = c.index(nx)
        l = len(c)-cs
        print(c[(k-cs)%l+cs])
        break
else:
    print(c[-1])

Submission status: Time Limit Exceeded

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

if N > K:
    ans = 0
    while K > 0:
        ans = A[ans] -1
        K -= 1
    print(ans+1)
else:
    count = 0
    a = 0
    visited = [0]
    while True:
        a = A[a]-1
        count += 1
        if a in visited:
            break
        visited.append(a)
    before_roop = visited.index(a)
    cycle = len(visited) - before_roop
    mod = (K - before_roop)%cycle
    print(visited[before_roop + mod] +1)

Submission status: Time Limit Exceeded

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

next_visit = 0
visited = [0]
for i in range(k):
  next_visit = a[next_visit] - 1
  if next_visit in visited:
    break
  visited.append(next_visit)

loop = visited[visited.index(next_visit):]
amari = (k - i - 1) % len(loop)

print(loop[amari]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l = list(map(int,input().split()))
t=0
for _ in range(k):
    t=l[t]-1
print(t+1)

Submission status: Time Limit Exceeded

Solution code:
N, K  = list(map(int,input().split()))
A  = list(map(int,input().split()))
A = [-1]+A
reached = []
now = 1
while now not in reached:
  reached.append(now)
  now = A[now]
ind = reached.index(now)
pre = reached[:ind]
loop = reached[ind:]
if K<=len(pre)-1:
  print(pre[K])
else:
  K -= (len(pre))
  K = K%len(loop)
  print(loop[K])

Submission status: Time Limit Exceeded

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

h = []
i = 0
s = 1

ans = 0
while i < k: 
  g = a[s-1]
  if g not in h:
    h.append(g)
    s = g
    i+=1
  else:
    c = h.index(g)
    l = (k-1-c) % (i-c)
    ans = h[c+l]
    break
    
if ans == 0:
  ans = h[-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

alr = []
now = 1
i = 0
while not now in alr:
    alr.append(now)
    now = A[now-1]
    i += 1
    if i == K:
        print(now)
        sys.exit()

place = alr.index(now)
circle = len(alr) - place
rem = (K - place) % circle
print(alr[place + rem])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
i=0
while i<k:
    ans=a[ans]-1
    i+=1
print(ans+1)

Submission status: Time Limit Exceeded

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    visited = [0]
    now = 0
    for k in range(K):
        now = A[now] - 1
        if now in visited:
            start = visited.index(now)
            visited = visited[start:]
            shuki = k + 1 - start
            print(visited[(K - start) % shuki] + 1)
            return
        visited.append(now)
    print(visited[-1] + 1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
L = []
S = set()
i = 1
cnt = 0
while not i in S or cnt != K:
    S.add(i)
    L.append(i)
    cnt += 1
    i = A[i]

if cnt == K:
    print(i)
else:
    j = L.index(i)
    ans = L[(j + (K - j) % (cnt - j)) % cnt]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=1
p=[]
for i in [0]*(n+1):
    p+=[l]
    l=a[l-1]
    if l in p:
        break
s=len(p)
q=p[p.index(l):]
r=s-len(q)
if k<=r:
    print(p[k])
else:
    print(q[(k-r)%(s-r)])

Submission status: Time Limit Exceeded

Solution code:
# 同じ町に二回到達したときに、前回たどり着いたときとの差を観る

import sys

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

X = [0] * (N + 1)
X[0] = 1

for i in range(1, K + 1):
    if A[X[i - 1] - 1] in X:
        # 前回の位置を取得
        hoge = X.index(A[X[i - 1] - 1])
        print(X[hoge + ((K - hoge) % ((i-1) - hoge + 1))])
        sys.exit()
    else:
        X[i] = A[X[i - 1] - 1]

print(X[K])

Submission status: Time Limit Exceeded

Solution code:
import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
d=dict()
for i,a in enumerate(A):
    d[i+1] = a
p=1
li = [1]
for i in range(k):
    #print(p,li)
    p = d[p]
    if p in li:
        pidx = li.index(p)
        cyc = i+1-pidx
        print(li[(k-pidx)%cyc+li.index(p)])
        sys.exit()
    li.append(p)
else:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
towns = [1]
prev = 1
count = 0
while len(towns) == len(set(towns)):
    next = a[prev - 1]
    towns.append(next)
    prev = next
    count += 1
    if count == k:
        print(next)
        sys.exit()
i = towns.index(next)
repeat = towns[i: -1]
unit = len(repeat)
rest = k - len(towns) + 2
print(repeat[(rest % unit) - 1])

Submission status: Time Limit Exceeded

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

start = 1
for _ in range(k):
  start = li[(start - 1)]
print(start)

Submission status: Time Limit Exceeded

Solution code:
n,k,*a=map(int,open(0).read().split())
a=[x-1 for x in a]
dist=[0]*n
cur=0
while True:
	nxt=a[cur]
	if k==1:
		print(nxt+1)
		break
	if dist[nxt]:
		k=(k-dist[nxt])%(dist[cur]-dist[nxt]+1)+dist[nxt]
		k-=1
		dist=[0]*n
		cur=nxt
	else:
		k-=1
		dist[nxt]=dist[cur]+1
		cur=nxt

Submission status: Time Limit Exceeded

Solution code:
a = input().split(" ")
N = eval(a[0])
K = eval(a[1])
dic = {}
b = input().split(" ")
for i in range(1, N + 1):
    dic[i] = eval(b[i - 1])
ans = 1
lst = []
length = 0
while K > 0:
    if ans in lst:
        left = lst.index(ans)
        right = length
        zq = right - left
        K = K % zq
        if K == 0:
            break
    else:
        lst.append(ans)
        length += 1
    ans = dic[ans]
    K -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
A =[0]+list(map(int,input().split()))
l= 1
a = A[1]

while a != 1:
  a = A[a]
  l += 1

m = k % l
b =1
for _ in range(m):
  b = A[b]
print(b)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
memory = [1]
cur = 1
count = 0
while True:
    if count == k:
        print(cur)
        exit()
    if a[cur] in memory:
        for i in range(len(memory)):
            if memory[i] == a[cur]:
                loop_begin = i
                break
        loop_end = count
        break
    else:
        memory.append(a[cur])
        cur = a[cur]
        count += 1
loop = memory[loop_begin:]
loop_length = loop_end-loop_begin+1
k -= loop_begin
print(loop[k%loop_length])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    res = K
    step = [-1 for _ in range(N)]
    que = queue.Queue()
    que.put(0)
    step[0] = 0
    while not que.empty():
        nc = que.get()
        nn = A[nc]
        nn -= 1
        res -= 1
        if step[nn] == -1:
            step[nn] = step[nc] + 1
            if res == 0:
                return print(nn + 1)
            que.put(nn)
        else:
            closer = [nn]
            while True:
                if A[nn] - 1 not in closer:
                    nn = A[nn] - 1
                    closer.append(nn)
                else:
                    break
            ans = res % len(closer)
            print(closer[ans] + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

a = A[0]

while (x<K):
    a = A[a-1]
    x += 1
    
print(a)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
list = list(map(int, input().split()))
val = list[0]
startcnt = 1
roopList = []
roopList.append(1)
while val not in roopList:
    roopList.append(val)
    val = list[val - 1]
    startcnt += 1
roopCount = len(roopList) - roopList.index(val)
if k <= startcnt:
    print(roopList[k])
else:
    roopList = roopList[roopList.index(val):]   
    print(roopList[(k - startcnt) % roopCount])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
a = 0
t = 1
d = 0
hoge_list = []
while a < k:
  hoge_list.append(t)
  t = a_list[t-1]
  a += 1
  if t in hoge_list:
    b = hoge_list.index(t)
    d += 1
    break
if d == 0:
  print(t)
else:
  e = (k-b)%(a-b)
  print(hoge_list[b+e])

Submission status: Time Limit Exceeded

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

path = [1]
for _ in range(N+10):
    next_A = As[path[-1] - 1]
    if next_A in path:
        break
    else:
        path.append(next_A)

before_loop = path.index(next_A)
loop_len = len(path) - before_loop

if K <= before_loop:
    print(path[K])
else:
    print(path[(K - before_loop) % loop_len + before_loop])

Submission status: Time Limit Exceeded

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

c=1
path=[]
d={}
l=0
while l<=k:
    if c in path:
        p=d[c]
        #print(p, path)
        pattern_l = l-p
        k-=((k-p)//pattern_l)*pattern_l
    path.append(c)
    l+=1
    d[c]=l-1
    c=A[c-1]
print(path[k])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for _ in range(k):
    c.append(a[c[-1]-1])
    
    if c.count(c[-1])==2:
        cs = c.index(c[-1])
        l = len(c)-cs-1
        print(c[(k-cs)%l+cs])
        break
else:
    print(c[-1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A = list(map(int, input().split()))
dic = {1:0}
now = 1
flag = 0
T = 0
log = [1]
for i in range(K):
  now = A[now-1]
  if now in log:
    flag=1
    T=i+1-dic[now]
    break
  dic[now] = i+1
  log.append(now)
if flag!=1:
  print(now)
else:
  print(log[(K-dic[now])%T+dic[now]])

Submission status: Time Limit Exceeded

Solution code:
def cal():

    n, times = input().split(" ")
    n = int(n)
    times = int(times)
    towns = list(map(int, input().split()))
    town = 1
    while times > 0:
        town = towns[town - 1]
        times -= 1
    print(town)




cal()

Submission status: Time Limit Exceeded

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

j=1

for i in range(1, k+1):
    j = a[j-1]
    
print(j)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
i=0
cnt=0
lcnt=0
sl=[0]*n
for p in range(k):
  if sl[i]==0:
    sl[i]=1
    i=l[i]-1
    cnt+=1
  elif sl[i]==1:
    sl[i]=2
    lcnt+=1
    i=l[i]-1
  else:
    c=(k-cnt)%lcnt
    if c!=0:
      for tmp in range(c):
        i=l[i]-1
        break
print(i+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=1
p=[]
while True:
    p+=[l]
    l=a[l-1]
    if l in p:
        break
s=len(p)
q=p[p.index(l):]
r=s-len(q)
if k<=r:
    print(p[k])
else:
    print(q[(k-r)%len(q)])

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	if K <= 10 ** 5:
		loc = 0
		for i in range(K):
			loc = A[loc] - 1
		print(loc + 1)
		return

	loc = 0
	for i in range(10 ** 5):
			loc = A[loc] - 1

	start = loc
	loop = [loc]
	loc = A[loc] - 1
	while loc != start:
		loop.append(loc)
		loc = A[loc] - 1

	M = len(loop)
	ans = loop[(K - 10 ** 5) % M]
	print(ans + 1)
	
	




if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

loop_counter = 0 # 何回目でループに達するか

start = 1
end = a[start-1]
road = [1]
while True:
    if end in road:
        # ループしている
        roop_start = end
        break
    else:
        road.append(end)
        start = end
        end = a[start-1]
roop_start_index = road.index(roop_start)
roop_length = len(road)-road.index(roop_start)
if k <= roop_start_index+1:
    print(road[k])
else:
    k -= roop_start_index
    k %= roop_length
    print(road[roop_start_index+k])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

stack = [0]
def dfs(a, k):
    global stack
    if k == 0:
        return a
    if k == -1:
        return stack[-1]
    next_a = A[a]-1
    if next_a in stack:
        idx = stack.index(next_a)
        n = len(stack)
        k %= (n - idx)
        res = dfs(next_a, k - 1)
    else:
        stack.append(next_a)
        res = dfs(next_a, k-1)
    return res

print(dfs(0, K) + 1)

Submission status: Time Limit Exceeded

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

x=1
while K:
    if K&1: x=A[x-1]
    K>>=1

    A2 = []
    for i in range(N):
        A2.append(A[A[i]-1])
    A=A2

print(x)

Submission status: Time Limit Exceeded

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

M = len(bin(K))-2

B = [[0]*N for _ in [0]*M]
B[0] = [a-1 for a in A]
for i in range(1,M):
    for j in range(N):
        B[i][j] = B[i-1][B[i-1][j]]

k = K
a = 0
while k>0:
    if k%2==1:
        a = B[0][a]
        k -= 1
        continue
    j = 1
    while k%(2**(j+1))==0:
        j += 1
    a = B[j][a]
    k -= 2**j
print(a+1)

Submission status: Time Limit Exceeded

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

c=1
path=[]
while len(path)<=k:
    if c in path:
        p=path.index(c)
        pattern_l = len(path)-p
        k-=((k-p)//pattern_l)*pattern_l
    path.append(c)
    c=A[c-1]
print(path[k])

Submission status: Time Limit Exceeded

Solution code:
n,k=[int(x) for x in input().split()]
p=[int(x)-1 for x in input().split()]
a=[0]
i=0
while p[i]!=0:
  a.append(p[i])
  i=p[i]
print(a[k%len(a)]+1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x:int(x) - 1, input().split()))
res = list(range(N))
while K:
    if K & 1:
        res = [res[A[i]] for i in range(N)]
    A = [A[A[i]] for i in range(N)]
    K >>= 1
print(res[0] + 1)

Submission status: Time Limit Exceeded

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

DOUB=[[-1]*(N+1) for i in range(62)]

DOUB[0]=[A[i] for i in range(N+1)]

for i in range(61):
    for j in range(N+1):
        DOUB[i+1][j]=DOUB[i][DOUB[i][j]]

NOW=1
while K:
    x=K.bit_length()-1
    NOW=DOUB[x][NOW]
    K-=1<<x
print(NOW)

Submission status: Time Limit Exceeded

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

maxD = K.bit_length() - 1

dp = [[0]*(N) for _ in range(maxD+1)]
for i in range(N):
    dp[0][i] = As[i]
for d in range(1, maxD+1):
    for i in range(N):
        dp[d][i] = dp[d-1][dp[d-1][i]]

iNow = 0  ###
for d in range(maxD+1):
    if K & (1<<d):
        iNow = dp[d][iNow]

print(iNow+1)

Submission status: Accepted

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,k=input2()
A=input_array()

# ある地点から循環に陥る
judge=[True]*n
tmps=[1] #循環手前
count=0 #参照地点

for i in range(2*(10**5)+1):
	if judge[count]==True:
		judge[count]=False
		count=A[count]-1
		tmps.append(count+1)
	else:
		break

loop_st=tmps.index(tmps[-1])
loops=tmps[loop_st:-1]


if k<loop_st:
	print(tmps[k])
else:
	k=k-loop_st
	k%=len(loops)
	print(loops[k])