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: Accepted

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

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

check = [0]*N

jump = 0

count = 0

while check[A[jump]-1] == 0 and count < K:
    n_jump = A[jump]-1
    check[n_jump] = check[jump]+1
    count += 1
    jump = n_jump

if count == K:
    key = max(check)
    ans = check.index(key)+1
else:
    count2 = 0
    key = max(check)
    jump = check.index(key)
    check2 = [0]*N
    while check2[A[jump]-1] == 0:
        n_jump = A[jump]-1
        check2[n_jump] = check2[jump]+1
        count2 += 1
        jump = n_jump
    amari = (K-count)%count2
    if amari == 0:
        key = max(check2)
        ans = check2.index(key)+1
    else:
        ans = check2.index(amari)+1
print(ans)

Submission status: Accepted

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

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

memo = [0]*(n+1)

for i in range(n):
    memo[i+1] = t[i]

move = 1

count = 0

check = [0]*(n+1)

while check[move] == 0 and count < k-1:
    check[move] += 1
    move=memo[move]
    count += 1

if k == count:
    print(memo[move])
else:
    count2 = 0
    check = [0]*(n+1)
    move_log = []
    while check[move] == 0:
        move_log.append(move)
        check[move] += 1
        move=memo[move]
        count2 += 1
    print(move_log[(k-count)%count2])

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
B = {1:1}
x = A[1]
st = 0
while True:
    if x not in B:
        B[x] = 1
        x = A[x]
    else:
        st = x
        break
x = 1
t = 0
while x!=st:
    x = A[x]
    t += 1
x = st
x = A[x]
T = 1
while x!=st:
    x = A[x]
    T += 1
if K<=t:
    x = 1
    cnt = 0
    while cnt<K:
        x = A[x]
        cnt += 1
    print(x)
else:
    K -= t
    K = K%T
    x = st
    cnt = 0
    while cnt<K:
        x = A[x]
        cnt += 1
    print(x)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
route = [now]
visited = set()
visited.add(now)
while A[now] not in visited:
    route.append(A[now])
    visited.add(A[now])
    now = A[now]
L = len(route)
looplen = L-route.index(A[now])
if K < L:
    print(route[K]+1)
else:
    print(route[L-looplen+(K-L)%looplen]+1)

Submission status: Accepted

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

table = [[0] * n for _ in [0] * 64]
table[0] = a

for i in range(61):
    for j in range(n):
        table[i + 1][j] = table[i][table[i][j]]

ans = 0
for i in range(61, -1, -1):
    if k >> i & 1:
        ans = table[i][ans]
print(ans + 1)

Submission status: Accepted

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

cnt = 0
cl = [-1]*(n+1)
cll = [1]
curr = 1
for i in range(min(n,k)):
    # print(curr)
    next_c = al[curr-1]
    if cl[next_c] != -1:
        # loop_start = (i+1)
        loop_start = cl[next_c]
        rem = k - (i+1)
        break
    else:
        cl[next_c] = i + 1
        cll.append(next_c)
    curr = next_c

else:
    print(curr)
    exit()

# print(rem)
loop_c = cll[loop_start:]
# print(loop_c)
last_ind = rem%len(loop_c)
ans = loop_c[last_ind]
print(ans)

Submission status: Accepted

Solution code:
#n = int(input())
n, k = map(int, input().split())
al = list(map(int, input().split()))
#al=[list(input()) for i in range(n)]
dic = {i: False for i in range(1, n+1)}
tel = [1]
bef = 1
tempInd = 1
while True:
    nex = al[bef-1]
    if dic[nex] == False:
        dic[nex] = tempInd
        tel.append(nex)
        bef = nex
        tempInd += 1
    else:
        lastind = dic[nex]-1
        break
tel.remove(1)
if len(tel) >= k:
    ans = tel[k-1]
else:
    repnum = len(tel)-lastind
    k -= len(tel)
    ans = tel[(k-1) % repnum + lastind]
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]-=1
doubling=[[0 for i in range(n)] for j in range(60)]
for i in range(n):
    doubling[0][i]=a[i]
for i in range(59):
    for j in range(n):
        doubling[i+1][j]=doubling[i][doubling[i][j]]
v=0
for d in range(60):
    if(k>>d &1):
        v=doubling[d][v]

print(v+1)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def dfs1(src):
    global steps
    if steps==rem:return src
    steps+=1
    return dfs1(g[src][0])
def dfs(src):
    global steps,done,boc,nic
    vis[src]=1
    steps+=1
    if steps-1==k:
        print(src)
        exit(0)
    dfn[src]=steps
    for neigh in g[src]:
        if not vis[neigh]:dfs(neigh)
        else:
            boc,done,nic=[neigh,steps,steps-dfn[neigh]+1]
            # print(done,boc,nic)
            return

n,k=list(map(int,stdin.readline().split()))
done,boc,nic=0,0,0
a=list(map(int,stdin.readline().split()))
g=defaultdict(list)
for i in range(1,n+1):
    g[i]+=[a[i-1]]
vis=[0]*(n+1)
dfn=[0]*(1+n)
steps=0
dfs(1)
# print(done,boc,nic)
left=k-done
rem=(left%nic)
if rem==0:rem=nic
steps=1
print(dfs1(g[boc][0]))

Submission status: Accepted

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

cnt = {}
for i in range(1, N+1):
    cnt[i] = 0

root = [0]
loop = []
now = 1
tmp = 0
amari = 0
while cnt[now] != 2:
    cnt[now] += 1
    root.append(now)
    if cnt[now] == 2:
        tmp = now
        break
    amari += 1
    now = A[now]

while cnt[tmp] == 2:
    loop.append(tmp)
    tmp = A[tmp]
    cnt[tmp] += 1

amari -= len(loop)

if K <= amari:
    ans = root[K+1]
else:
    ind = amari + (K-amari)%len(loop) + 1
    ans = root[ind]

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0] * n
c = ['Y'] * n
c[0] = 'N'
x = 0
y = 1
while x != k:
    c[y-1] = 'N'
    x += 1
    y = a[y-1]
    b[x-1] = y
    if c[y-1] == 'N':
        break
if x != k:
    y = b.index(a[y-1])
    k -= x
    k %= (x-y)
    c = b[y:x]
    print(c[k-1])
else:
    print(y)

Submission status: Accepted

Solution code:
import sys

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


N,K = map(int,input().split())
A=list(map(int,input().split()))
P=[True]*N
P[0]=False
i,a=1,0
while 1:
  a+=1
  if P[A[i-1]-1]:
    P[A[i-1]-1]=False
    i=A[i-1]
  else:
    i=A[i-1]
    break
if a>=K:
  i=1
  for _ in range(K):
    i=A[i-1]
  print(i)
else:
  K-=a
  a,j=0,i
  while 1:
    a+=1
    if A[j-1]==i:
      break
    j=A[j-1]
  K%=a
  for _ in range(K):
    i=A[i-1]
  print(i)

Submission status: Accepted

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

count = 0
point = 0
check[0] = 1
path = [0]
for i in range(min(n, k)):
    if i == 0 or check[point] == 0:
        check[point] = i+1
        point = a[point]
        path.append(point)
    else:
        break


cycle_len = len(path)-check[point]
pre = check[point]
if pre > k:
    print(path[k])
else:
    k -= pre
    k %= cycle_len
    print(path[pre+k]+1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
t=[0 for i in range(n+1)]
town=1
for i in range(n+1):
    t[town]+=1
    if t[town]==2:
        break
    town=a[town-1]
r=0
sy=0
town=1
while t[town]!=2:
    r+=1
    town=a[town-1]
for i in range(n):
    sy+=1
    town=a[town-1]
    if t[town]==2:
        break
town=1
if r>=k:
    for i in range(k):
        town=a[town-1]
    print(town)
else:
    for i in range(r):
        town=a[town-1]
    k=k-r
    m=k//sy
    k=k-m*sy
    for k in range(k):
        town=a[town-1]
    print(town)

Submission status: Accepted

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

color=["white" for _ in range(n+1)]
DP,index=[],1

while 1:
    if color[index]=="white":color[index]="gray"
    elif color[index]=="gray":color[index]="black"
    DP.append(A[index])
    index=A[index]
    if color[index]=="black":break

repeat=[]
for i in DP:
    if color[i]=="black":
        repeat.append(i)
        if repeat[0]==i and len(repeat)!=1:
            repeat.pop()
            break
length=len(repeat)
cnt=0
for i in DP:
    if repeat[0]==i:break
    cnt +=1

if k<=cnt+length:
    print(DP[k-1])
else:
    k -=cnt
    k %=length
    print(repeat[k-1])

Submission status: Accepted

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

visited = [-1]+[False]*n

i = 1
while True:
    if visited[i]:
        fragrant = i
        break
    else:
        visited[i] = True
        i = l[i]

i = fragrant
cnt = 1
while l[i] != fragrant:
    cnt += 1
    i = l[i]
# print(cnt)

i = 1
while k > 0:
    i = l[i]
    k -= 1
    if i == fragrant:
        k %= cnt
print(i)

Submission status: Accepted

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

done = {0}
rt = [0]
loop_point = 0
while True:
    p = rt[-1]
    np = A[p]
    if np in done:
        loop_point = np
        break
    done.add(np)
    rt.append(np)
if K < len(rt):
    ans = rt[K] + 1
else:
    K -= len(rt)
    rt = rt[rt.index(loop_point):]
    ans = rt[K%len(rt)] + 1
print(ans)

Submission status: Accepted

Solution code:
import heapq

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
way = [0]
hq = [0]
heapq.heapify(hq)
posi = 0
cycle = 0
while True:
    if binary_search(hq, a[posi]) != -1:
        rest = way.index(a[posi])
        cycle -= (rest - 1)
        break
    way.append(a[posi])
    heapq.heappush(hq, a[posi])
    posi = a[posi]
    cycle += 1
# print(way)
# print(cycle)
if k < len(way):
    print(way[k] + 1)
else:
    print(way[(k-rest) % cycle + rest] + 1)

Submission status: Accepted

Solution code:
import heapq

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
way = [0]
hq = [0]
heapq.heapify(hq)
posi = 0
cycle = 0
while True:
    if binary_search(way, a[posi]) != -1:
        rest = way.index(a[posi])
        cycle -= (rest - 1)
        break
    way.append(a[posi])
    heapq.heappush(hq, a[posi])
    posi = a[posi]
    cycle += 1
# print(way)
# print(cycle)
if k < len(way):
    print(way[k] + 1)
else:
    print(way[(k-rest) % cycle + rest] + 1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = [-1] * self.n
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = cnt
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既に探索していたら
                    if ignore[to] < cnt:
                        break
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = cnt
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to

"""
N, A = getNM()
A -= 1
K = getN()
B = [i - 1 for i in getList()]
roop = Roop(B)
print(roop.move(A, K) + 1)

"""
# ABC167 D - Teleporter
N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)



"""
# ABC175 D - Moving Piece
N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()
# ループ検出
roop = Roop(P)

# 各ループごと調べる
ans = -float('inf')
for r in roop.roops:
    n = len(r)
    # ループに対応するスコアリストを用意
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    # １回ループすると何点getできるか
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        # 長さ1からtまでの区間の総和の最大値を探索
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)
"""

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

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

    c = []
    mark = [-1]*n
    pos,l = 0,0
    while 1:
        if mark[pos] >= 0:
            l = mark[pos]
            break
        mark[pos] = len(c)
        c.append(pos)
        pos = a[pos] - 1
    if k <= l:
        print(c[k] + 1)
    else:
        k -= l
        print(c[l + k%(len(c) - l)] + 1)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = {}
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = 1
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既にループ作成済なら
                    if self.roop_dict[to] >= 0:
                        break
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    if len(opt[self.opt_dic[to]:]) > 0:
                        self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = 1
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to


# ABC167 D - Teleporter
N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)


"""
# ABC175 D - Moving Piece
N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()
# ループ検出
roop = Roop(P)

# 各ループごと調べる
ans = -float('inf')
for r in roop.roops:
    n = len(r)
    # ループに対応するスコアリストを用意
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    # １回ループすると何点getできるか
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        # 長さ1からtまでの区間の総和の最大値を探索
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)
"""

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        # ループ検出
        self.roops = []
        # iはどのループのものか
        self.roop_dict = [-1] * self.n
        # ループ内の何番目にあるか
        self.opt_dic = {}
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            # opt内の何番目にあるか
            self.opt_dic[i] = 0
            c = 1
            # 探索したらフラグを立てる
            ignore[i] = 1
            # i → array[i]
            to = array[i]
            # ループが詰まるまで回す
            while True:
                if ignore[to] >= 0:
                    # 既にループ作成済なら
                    if self.roop_dict[to] >= 0:
                        break
                    # 作成してないならループ作成
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    # 次のループはcnt + 1番
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = 1
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    # xがどの番号のループにあるか
    def roop_n(self, x):
        return self.roop_dict[x]

    # xが入っているループは何か
    # ループ内になければFalse
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    # ループの大きさ
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    # xからk回移動してどの場所に行けるか
    def move(self, x, k):
        if k == 1:
            return x + 1
        cnt = k
        to = x
        # ループに入る前にどのルートを通ったか
        # スタート地点から既にループに入っていた場合、headは空になる
        head = []
        # ループ脱出後どのルートを通るか
        tail = []
        # 何回ループしたか
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            # まだループしておらず、踏んだ場所がループ内にある場合
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            # ループ前なら
            if time == -1:
                head.append(to)
            # ループ後なら
            else:
                tail.append(to)
        # 例: N, K = 6 727202214173249351
        # A = [6, 5, 2, 5, 3, 2]の時
        # 1回目の移動 1 → 6
        # 2回目の移動 6 → ### ここからループが始まる ### → 2
        # ... 242400738057749783回ループ
        # 727202214173249351回目の移動 3 → 2
        # to, head, tail, time = (1, [5], [1], 242400738057749783)
        return to

"""
# ABC 030 へんてこ辞書
N, A = getNM()
A -= 1
K = getN()
B = [i - 1 for i in getList()]
roop = Roop(B)
for i in range(N):
    print(roop.move(i, K) + 1)
"""

# ABC167 D - Teleporter
N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)

"""
# ABC175 D - Moving Piece
N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()
# ループ検出
roop = Roop(P)

# 各ループごと調べる
ans = -float('inf')
for r in roop.roops:
    n = len(r)
    # ループに対応するスコアリストを用意
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    # １回ループすると何点getできるか
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        # 長さ1からtまでの区間の総和の最大値を探索
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)
"""

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()
check_num = [-1] * n
idx = 0
cnt = 1
while 1:
    idx = a[idx] - 1
    if check_num[idx] != -1:
        s = check_num[idx] - 1
        cnt -= 1
        break
    check_num[idx] = cnt
    cnt += 1

if cnt >= k:
    for i in range(n):
        if check_num[i] == k:
            print(i+1)
            quit()
else:
    roop_num = cnt - s
    x = (k - (s + 1)) % roop_num
    for i in range(n):
        if check_num[i] - s - 1 == x:
            print(i+1)
            quit()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
a = LI()

check_num = [-1] * n
idx = 0
cnt = 1
while 1:
    idx = a[idx] - 1
    if check_num[idx] != -1:
        s = check_num[idx] - 1
        break
    check_num[idx] = cnt
    cnt += 1
cnt -= 1
if cnt >= k:
    for i in range(n):
        if check_num[i] == k:
            print(i+1)
            break
else:
    x = cnt - s
    y = (k - (s + 1)) % x
    for i in range(n):
        if check_num[i] == s + y + 1:
            print(i+1)
            break