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

Solution (Python):
import sys
import re
import queue
import collections
import math
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,K = i_map()
	A = i_list()

	for i in range(0,len(A)):
		A[i] = A[i] - 1

	lengthA = math.ceil(math.log2(K))

	next = [[0 for _ in range(N)] for _ in range(lengthA)]
	
	for i in range(0,N):
		next[0][i] = A[(i)%(N)]

	for i in range(1,lengthA):
		for j in range(0,N):
			next[i][j] = next[i-1][next[i-1][j]]

	current = 0

	for i in range(0,lengthA):
		if((1 << i) & K):
			current = next[i][current]

	print(current+1)

	return

if __name__ == '__main__':
	main()

Solution (Python):

def input2():
	return map(int,input().split())


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])

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

    seen = {}
    find_cnt = {}
    cnt = 0
    dst = 1
    while K:
        if dst in seen:
            cycle = cnt - seen[dst]
            K %= cycle
            print(find_cnt[seen[dst]+K])
            return

        else:
            seen[dst] = cnt
            find_cnt[cnt] = dst

        dst = A[dst]
        cnt += 1
        K -= 1

    print(dst)


if __name__ == "__main__":
    main()

Solution (Python):
class Doubling():
    def __init__(self,N,log_k,perm):
        """
        与えられた順列のダブリング配列を作成する.

        Parameters
        ----------
            N :  int
                順列の数
            log_k : int
                最大移動回数の対数(切り上げ)
            perm : [int]
                1-indexed の順列が格納されたリスト
        """
        self.N = N
        self.log_k = log_k
        self.doubling = [[0]*(self.N+1) for _ in range(log_k)]

        for i in range(1,self.N+1):
            self.doubling[0][i] = perm[i]

        for j in range(1,self.log_k):
            for i in range(1,self.N+1):
                prev = self.doubling[j-1][i]
                self.doubling[j][i] = self.doubling[j-1][prev]
        
    def query(self,pos,k):
        """
        位置iからk回移動したときの移動先を計算する.

        Parameters
        ----------
            pos : int
                移動元の位置
            k : int
                移動回数(1<=k<=2^(log_k+1)-1)

        Returns
        ----------
            dest : int
                移動先の位置
        """
        for i in range(self.log_k):
            if k & (1<<i) == 0:continue
            pos = self.doubling[i][pos]
        dest = pos
        
        return dest

def main():
    n,k = tuple([int(t)for t in input().split()])

    a = [int(t) for t in input().split()]

    a.insert(0,0)
    log_k = k.bit_length()+1

    doubling = Doubling(n,log_k,a)
    print(doubling.query(1,k))

    
if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
ai = list(map(int, input().split()))
for i in range(N):
    ai[i] -= 1
    
import math
dv = []
dv.append(ai)
for k in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        

now = 0
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        
        now = dv[i][now]
print(now + 1)

Solution (Python):
N, K = map(int, input().split())
ai = list(map(int, input().split()))
for i in range(N):
    ai[i] -= 1
    
import math
dv = []
dv.append(ai)
for k in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)
        
now = 0
for i in a:
    now = dv[i][now]
print(now + 1)

Solution (Python):
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 1000000007

n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

tmp = [0 for i in range(n + 1)]
cnt = 0
res = 1

while cnt < k:
    cnt += 1
    if tmp[res] == 0:
        tmp[res] = cnt
    else:
        cnt += (k - cnt) // (cnt - tmp[res]) * (cnt - tmp[res])
        tmp[res] = cnt
    res = A[res - 1]

print(res)

Solution (Python):
n, k = map(int, input().split())
an = list(map(int, input().split()))
for i in range(n):
    an[i] -= 1
    
import math
dv = []
dv.append(an)
K = k
N = n
for _ in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)

for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        


a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)
        
now = 0
for i in a:
    now = dv[i][now]
        
print(now + 1)

Solution (Python):
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
town=set()
town.add(1)
town_ls=[1]
now=1
for i in range(min([K,N])):
  now=ls[now-1]
  if now in town:
    break
  town.add(now)
  town_ls.append(now)

if i+1==K:
  print(now)
else:
  L=i+1
  S=town_ls.index(now)
  loop=L-S
  
  x=(K-S)%loop+S
  print(town_ls[x])

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
a=lnii()

x=0
x_list=[1]
x_table=[0 for i in range(n+1)]
x_table[1]=1

for i in range(k):
  nx=a[x]

  if x_table[nx]!=0:
    inx=x_list.index(nx)
    loop=x_list[inx:]
    zan=k-i

    q=zan%len(loop)

    nx=loop[q-1]
    break

  else:
    x=nx-1
    x_list.append(nx)
    x_table[nx]+=1

print(nx)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
a=lnii()

x=0
x_list=[1]
x_table=[0 for i in range(n+1)]
x_table[1]=1

for i in range(k):
  nx=a[x]

  if x_table[nx]!=0:
    inx=x_list.index(nx)
    loop=x_list[inx:]
    zan=k-i

    q=zan%len(loop)

    nx=loop[q-1]
    break

  else:
    x=nx-1
    x_list.append(nx)
    x_table[nx]+=1

print(nx)

Solution (Python):

url = "https://atcoder.jp/contests/abc162/tasks/abc162_d"
import itertools


def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    route = []
    istuka = [0] * (n+1)
    next = 1
    
    for _ in range(k):
        if istuka[next] == 1:
            break
        else:
            istuka[next] = 1
            route.append(next)
        next = a[next - 1]
    if n >= k:
        print(next)
        exit()
    ans = route[route.index(next):]
    idx = (k - route.index(next)) % len(ans)
    print(ans[idx])



if __name__ == '__main__':
    main()

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

path = [0]*(N+1)
visited = set()

pos = 1
for i in range(N+1):
    if pos in visited: break
    path[i] = pos
    visited.add(pos)
    pos = A[pos]

loc = path.index(pos)
head = path[:loc]
rep = path[loc:i]

if K < len(head):
    print(head[K])
else:
    print(rep[(K - len(head)) % len(rep)])

Solution (Python):
N,K = map(int, input().split())
A = list(map(int, input().split()))
k = K.bit_length()
dv = [[0]*N for _ in range(k)]
dv[0] = [a-1 for a in A]
for turn in range(1,k):
    for town in range(N):
        dv[turn][town] = dv[turn-1][dv[turn-1][town]]

a = 0
for i in range(k):
    if (K>>i)&1:
        a = dv[i][a]
        
print(a+1)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
data=[0]*(n+1)
data[1]=1
ans=[1]
res=0
for i in range(n):
  p=a[res]
  if data[p]==0:
    data[p]=1
    ans.append(p)
    res=p-1
  else:
    res=ans.index(p)
    break
if len(ans)>k:
  print(ans[k])
else:
  m=len(ans)-res
  k-=res
  d=k%m
  print(ans[res+d])

Solution (Python):


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

b = [-1]*(n+1) 
tmp = [] 
here = 1
count = 0 

while True:
    if b[here] != -1: 
        roop = count - b[here] 
        if k < count: 
            print(tmp[k])
        else:
            new_tmp = tmp[b[here]:]
            s = k-b[here]
            print(new_tmp[s%roop])
        break
    b[here] = count
    count += 1
    tmp.append(here)
    here = a[here-1]

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

next = [[0]*n for _ in range(60)]

for v in range(n):
    next[0][v] = a[v]-1
for d in range(60-1):
    for v in range(n):
        next[d+1][v] = next[d][next[d][v]]
        
v = 0
for d in range(60):
    if k>>d&1:
        v = next[d][v]
        
print(v+1)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in range(1, n+1):
    d[i] = 0
l = [1]
x = 1
if n >= k:
    for i in range(k):
        x = a[x-1]
    print(x)
    exit()
for i in range(n):
    x = a[x-1]
    if d[x] == 1:
        k -= l.index(x)
        print(l[l.index(x):][k%(l.index(x)-len(l))])
        exit()
    l.append(x)
    d[x] += 1
print(x)

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

timestep_pos_map = []  
pos_timestep_map = {}  

timestep_pos_map.append(1)  
pos_timestep_map[1] = 0     

for timestep in range(1, min(K + 1, N + 1 + 1)):
    prev_pos = timestep_pos_map[-1]
    cur_pos = A[prev_pos - 1]

    if timestep == K:
        print(cur_pos)
        exit()

    if cur_pos in pos_timestep_map:
        prev_timestep = pos_timestep_map[cur_pos]
        interval = timestep - prev_timestep
        offset = (K - prev_timestep) % interval
        print(timestep_pos_map[prev_timestep + offset])
        exit()

    timestep_pos_map.append(cur_pos)
    pos_timestep_map[cur_pos] = timestep

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
c = 0
List = []
check = [-1]*N
tmp = 1
for i in range(min(N+1,K)):
    tmp2 = A[tmp-1]
    List.append(tmp2)
    if(check[tmp2-1] >= 0):
        tmp3 = check[tmp2-1]
        del List[-1]
        break
    else:
        check[tmp2-1] = i
        tmp = tmp2
        c += 1
if(c >= K):
    print(List[K-1])
else:
    List2 = List[tmp3:]
    if(c == len(List2)):
        print(List2[(K%len(List2))-1])
    else:
        K -= c
        print(List2[(K%len(List2))-1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]

log_K = 1
while 1 << log_K < K:
    log_K += 1

D = [[0] * N for _ in range(log_K)]
for i in range(N):
    D[0][i] = A[i]
for k in range(log_K - 1):
    for i in range(N):
        D[k + 1][i] = D[k][D[k][i]]


now = 0
k = 0
while K > 0:
    if K & 1:
        now = D[k][now]
    K = K >> 1
    k += 1
print(now + 1)

Solution (Python):
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
k-=p
loop=len(w)-p
print(w[p+k%loop])

Solution (Python):
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
if p==0:
    print(w[k%len(w)])
else:
    p=w.index(t)
    k-=p
    loop=len(w)-p
    print(w[p+k%loop])

Solution (Python):


import numpy as np






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

    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        
        dp[h] = np.take(dp[h - 1], dp[h - 1])

    node = 1
    
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

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


d = [[-1] * n for _ in range(70)]

for i in range(n):
    d[0][i] = a[i] - 1

for i in range(1, 70):
    for j in range(n):
        d[i][j] = d[i - 1][d[i - 1][j]]

dst = 0
while k:
    i = 70
    while pow(2, i) & k <= 0:
        i -= 1

    dst = d[i][dst]
    k -= pow(2, i)

print(dst + 1)

Solution (Python):
N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))

id = [-1] * (N + 1)
x = 1
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

c = l - id[x]
if K < l:
    print(a[K])
else:
    K -= l
    print(a[id[x] + K % c])

Solution (Python):
if __name__ == '__main__':

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

    B = set()
    cnt = 0
    ind = 1
    startind = 0
    D = []
    while True:
        if A[ind] not in B:
            B.add(ind)
            D.append(ind)
            cnt += 1
            ind = A[ind]
        else:
            B.add(ind)
            D.append(ind)
            cnt += 1
            startind = A[ind]
            break

    C = set()
    ind = startind
    ANS = []
    while True:
        if A[ind] not in C:
            C.add(ind)
            ind = A[ind]
            ANS.append(ind)
        else:
            C.add(ind)
            ANS.append(A[ind])
            break

    if k >= cnt:
        tmp = k - cnt
        tmp = tmp % (len(C))
        print(ANS[tmp-1])
    else:
        print(D[k])

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
B[0]=1
if B[0] in A:c=B[0]
for i in range(1,N):
  B[i]=A[B[i-1]-1]

d=B.index(B[-1])+1
if K<=N:print(B[K]);exit()
print(B[d-1+(K+1-d)%(N-d)])

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[0]=1
if B[0] in A:c=B[0]
for i in range(1,N+1):
  B[i]=A[B[i-1]-1]

d=B.index(B[-1])+1
if K<=N:print(B[K]);exit()
print(B[d-1+(K+1-d)%(N+1-d)])

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[0]=1;c=0;d=0
if B[0] in A:c=B[0]
for i in range(1,N+1):
  B[i]=A[B[i-1]-1]

d=B.index(B[-1])+1
if K<=N:print(B[K]);exit()

print(B[d-1+(K+1-d)%(N+1-d)])

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[0]=1;c=0;d=0
if B[0] in A:c=B[0]
for i in range(1,N+1):
  B[i]=A[B[i-1]-1]



d=B.index(B[-1])+1





if K<=N:print(B[K]);exit()
if (K+1-d)%(N+1-d)==0:print(B[-1])
else:print(B[d-1+(K+1-d)%(N+1-d)])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))

I = [-1] * (N + 1)
S = []
idx = 1
while I[idx] == -1:
    S.append(idx)
    I[idx] = len(S)
    idx = A[idx]


start_idx = I[idx] - 1
num_circles = len(S) - start_idx


if K < len(S) - 1:
    ans = S[K]
else:
    K -= start_idx
    div, mod = divmod(K, num_circles)
    ans = S[start_idx + mod]
print(ans)

Solution (Python):
N,K=map(int,input().split())
Alist=list(map(int,input().split()))
already=[1]
alreadyset={1}
last=1
while True:
    if Alist[last-1] in alreadyset:
        start=already.index(Alist[last-1])
        break
    already.append(Alist[last-1])
    alreadyset.add(Alist[last-1])
    last=Alist[last-1]
roop=len(already)-start
if K-len(already)<0:
    print(already[K])
else:
    index=(K-start)%roop+start
    while not start<=index<len(already):
        index=index%roop+start
    print(already[index])

Solution (Python):


import numpy as np






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

    warps = list(map(int, input().split()))
    warps = [0] + warps
    

    
    order_num = [0 for i in range(len(warps))]
    path_history = []

    node = 1
    while order_num[node] == 0:
        path_history.append(node)
        order_num[node] = len(path_history)
        node = warps[node]

    
    
    begin = order_num[node]
    

    if k <= begin:
        print(path_history[k])
    else:
        
        
        leng = len(path_history) - order_num[node] + 1
        
        index = (k - (begin - 1)) % leng
        
        print(path_history[begin - 1 + index])


main()

Solution (Python):


import numpy as np






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

    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    order_num = np.zeros(len(warps) + 1, dtype=int)
    path_history = []

    node = 1
    while order_num[node] == 0:
        path_history.append(node)
        order_num[node] = len(path_history)
        node = warps[node]

    
    
    begin = order_num[node]
    

    if k <= begin:
        print(path_history[k])
    else:
        
        
        leng = len(path_history) - order_num[node] + 1
        
        index = (k - (begin - 1)) % leng
        
        print(path_history[begin - 1 + index])


main()

Solution (Python):


import sys
import numpy as np






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

    
    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Solution (Python):


import sys
import numpy as np


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


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

    
    warps = list(map(int, input().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Solution (Python):


import sys
import numpy as np


def main():
    n, k = map(int, sys.stdin.buffer.readline().split())

    warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Solution (Python):


import sys
import numpy as np


def main():
    n, k = map(int, sys.stdin.buffer.readline().split())

    warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()

Solution (Python):
from math import log2

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

logk = int(log2(k))+1
db = [ [0]*n for _ in range(logk) ]
for ni in range(n): 
    db[0][ni] = al[ni]-1
for ki in range(logk-1):
    for ni in range(n):
        db[ki+1][ni] = db[ki][db[ki][ni]]

now = 0
for i in range(logk):
    if k&(1<<i) > 0:
        now = db[i][now]
print(now+1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
doubling = [[0]*N for _ in range(61)]
doubling[0] = list(map(lambda x:x-1, As))

for i in range(1, 61):
    for j in range(N):
        doubling[i][j] = doubling[i-1][doubling[i-1][j]]

now = 0
for i in range(61):
    if (K>>i)&1:
        now = doubling[i][now]
print(now+1)

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

logk = k.bit_length()
doubling = []
for _ in range(logk):
  tmp = [0] * n
  doubling.append(tmp)

for i in range(n):
  doubling[0][i] = a[i] - 1

for i in range(1,logk):
  for j in range(n):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]

now = 0
pos = 0
while k:
  if k & 1:
    now = doubling[pos][now]
  k = k >> 1
  pos += 1

print(now+1)

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

count = 0

stack = set()
visited = []
visited_set = set()
endf = False

current = 0
while True:
    i = A[current]-1
    visited_set.add(current)
    visited.append(current)

    if not i in visited_set:
        current = i
        count += 1
    else:
        leng = len(visited_set)
        roop_len = leng - visited.index(i)
        header_len = leng - roop_len
        break

    if count >= K:
        endf = True
        print(i+1)
        break

if not endf:
    roop_ind = (K - header_len + 1) % roop_len
    if roop_ind == 0:
        print(visited[-1]+1)
    else:
        print(visited[header_len + roop_ind-1]+1)

Solution (Python):
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    P = [p]
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
        P.append(p)
    front = P[:L]
    if L != N:
        cycle, end = P[L:R], P[L:L+(N-L)%period]
        cnt = (N-L)//period
    return front, cycle, end, cnt




import sys
input = sys.stdin.readline

def lift(x): return A[x-1]

N, K = map(int, input().split())
A = list(map(int, input().split()))
front, cycle, end, cnt = cycle_getter(K+1,1)

print((front+cycle+end)[-1])

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dic={}
wk=1
start=0
for i in range(1,n+1):
  wk=a[wk-1]
  if wk in dic:
    start=dic[wk]
    break
  dic[wk]=i
end=len(dic)
loopcnt=end-start+1
keys=list(dic.keys())
if k<start:
  print(keys[k-1])
else:
  chk=(k-start+1)%loopcnt
  if chk==0:
    chk=loopcnt
  print(keys[(start-1)+chk-1])

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dic={}
wk=1
start=0
for i in range(1,n+1):
  wk=a[wk-1]
  if wk in dic:
    start=dic[wk]
    break
  dic[wk]=i
end=len(dic)
loopcnt=end-start+1
keys=list(dic.keys())
if k<start:
  print(keys[k-1])
else:
  chk=(k-start+1)%loopcnt
  if chk==0:
    chk=loopcnt
  print(keys[(start-1)+chk-1])

Solution (Python):
from collections import defaultdict

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

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

visited = [0] * N

current = 0
i = 1
while i <= K:
    current = A[current] - 1
    if visited[current] == 0:
        visited[current] = i
    else:
        loop = i - visited[current]
        num_loop = (K - i) // loop
        i += loop * num_loop

    i += 1

ans = current + 1
print(ans)

Solution (Python):
from collections import deque

N, K = map(int, input().split())
towns = [0] + list(map(int, input().split()))
checked = [-1 for _ in range(N+1)]
checked[1] = 0
next = towns[1]
count = 1
    
while(checked[next] < 0):
  checked[next] = count
  count += 1
  next = towns[next]
loop = count - checked[next]
pos = 0
if K >= count:
  pos = checked[next] + (K-checked[next])%loop
else:
  pos = K
for i in range(1, N+1):
  if checked[i] == pos:
    print(i)
    exit()

Solution (Python):
N, K = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))
n = 1
c = 0
while n <= K:
    n *= 2
    c += 1

L = [[0]*(N+1) for _ in range(c)]
L[0] = A
for i in range(1, c):
    for j in range(N+1):
        L[i][j] = L[i-1][L[i-1][j]]


p = 1
for i in range(c):
    if (K >> i) & 1:
        p = L[i][p]
print(p)

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

visited = [0] * N
path = []
now_town = 1
while(True):
    visited[now_town-1] = 1
    path.append(now_town)
    now_town = As[now_town-1]
    if visited[now_town-1] == 1:
        break
index = path.index(now_town)
loop = path[index:len(path)]
loop_len = len(loop)
if index < K:
    k = K - index
    r = k % loop_len
    print(loop[r])
else:
    print(path[K])

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
G = [1]

for n in range(N-1):
  G.append(A[G[n]-1])

if len(G)<K:
  a = G.index(G[-1])
  b = len(G)-a-1
  K = (K-a)%b+a

print(G[K])

Solution (Python):
import sys
N , K = list(map(int, input().split()))
As = list(map(int, input().split()))
As = [0]+As
Came = [-1]*(N+1)

s = 1
i = 0

while True:
    if As[s] == s:
        print(s)
        sys.exit()
    elif i >=K:
        print(s)
        sys.exit()
    elif Came[s]>=0:
        break
    Came[s] = i
    i+=1
    s = As[s]

T = i - Came[s]

L = K - Came[s]

Q = L % T

print(Came.index(Came[s]+Q))

Solution (Python):
n, k = [int(x) for x in input().split()]
a_list = [int(x) - 1 for x in input().split()]
ci = 0
while k:
    if k & 1:
        ci = a_list[ci]
    k >>= 1
    a_list = [a_list[a_list[i]] for i in range(n)]
print(ci + 1)

Solution (Python):
n, k = [int(x) for x in input().split()]
a_list = [int(x) - 1 for x in input().split()]

ci = 0
temp_dict = {0: 0}
temp_list = [0]
for i in range(1, k + 1):
    temp = a_list[ci]
    if temp in temp_dict:
        ci = temp_list[(k - i) % (i - temp_dict[temp]) + temp_dict[temp]]
        break
    temp_dict[temp] = i
    temp_list.append(temp)
    ci = temp
print(ci + 1)

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

dic = {}
list_town = []
set_town = set()
town = 1

for i, v in enumerate(A):
    dic[i+1] = v

for _ in range(K):
    list_town.append(town)
    set_town.add(town)
    town = dic[town]
    if town in set_town:
        stop_town = town
        break

if N <= K:
    list_first_split = list_town[:list_town.index(stop_town)]
    list_second_split = list_town[list_town.index(stop_town):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = [a-1 for a in list(map(int, input().split()))]
    visited = [0] * N
    bofore_loop_route = []
    route = []
    town = A[0]
    while True:
        if visited[town] == 0:
            visited[town] = 1
            route.append(town)
            town = A[town]
        else:
            before_loop = route.index(town)
            bofore_loop_route = route[:before_loop]
            route = route[before_loop:]
            break
    if K <= len(bofore_loop_route):
        print(bofore_loop_route[K-1] + 1)
    else:
        idx = ((K - before_loop) % len(route)) - 1
        print(route[idx] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
n,k = map(int,input().split())
b = [bi-1 for bi in list(map(int,input().split()))]
a = 0

f = [0]*n
c = 1
for i in range(k):
    if f[a]:
        k %= c-f[a]
        for i in range(k):
            a = b[a]
        print(a+1)
        break
    f[a] = c
    k -= 1
    c += 1
    a = b[a]
else:
    print(a+1)

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

dic = {}
list_town = []
set_town = set()
town = 1

for i, v in enumerate(A):
    dic[i+1] = v

for _ in range(K):
    list_town.append(town)
    set_town.add(town)
    town = dic[town]
    if town in set_town:
        stop_twon = town
        break

if N <= K:
    list_first_split = list_town[:list_town.index(stop_twon)]
    list_second_split = list_town[list_town.index(stop_twon):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

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

dic = {}
for i, v in enumerate(A):
    dic[i+1] = v

town = 1
s = set()
l = []
for _ in range(K):
    l.append(town)
    s.add(town)
    town = dic[town]
    if town in s:
        stop_twon = town
        break
if N <= K:
    list_first_split = l[:l.index(stop_twon)]
    list_second_split = l[l.index(stop_twon):]
    print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])
else:
    print(town)

Solution (Python):
N, K = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
db = [[0]*N for _ in range(60)]
db[0] = A[:]
for i in range(1,60):
  for j in range(N):
    db[i][j] = db[i-1][db[i-1][j]]
ans = p = 0
while K>0:
  if K%2==1:
    ans = db[p][ans]
  p += 1
  K >>= 1
print(ans+1)

Solution (Python):
N, K = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
db = [[0]*N for _ in range(100)]
db[0] = A[:]
for i in range(1,100):
  for j in range(N):
    db[i][j] = db[i-1][db[i-1][j]]
ans = p = 0
while K>0:
  if K%2==1:
    ans = db[p][ans]
  p += 1
  K >>= 1
print(ans+1)

Solution (Python):
from collections import defaultdict

N,K = map(int, input().split())
A = [int(i) for i in input().split()]
used_dict = defaultdict(int)
used_dict[0] += 1
now_town = 0
flag = False

for i in range(min(N,K)):
    now_town = A[now_town]-1
    if used_dict[now_town]:
        used_dict[now_town] += 1
        break
    used_dict[now_town] += 1
else:
    flag = True

if not flag:
    now_town2 = 0
    cnt = 0
    while 1:
        if now_town2 == now_town:
            for _ in range((K-cnt)%(i-cnt+1)):
                now_town = A[now_town]-1
            break
        now_town2 = A[now_town2]-1
        cnt += 1
print(now_town+1)