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):
n,k=map(int,input().split())
a=list(map(int,input().split()))
adj=[1]*n
b=[1]
now=0
while adj[now]:
  adj[now]=0
  now=a[now]-1
  b.append(now+1)
loop_start=b.index(b[-1])
loop=b[loop_start:-1]
p=len(loop)
if k<loop_start:
  print(b[k])
else:
  k-=loop_start
  k%=p
  print(loop[k])

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(lambda x: int(x)-1,input().split()))
    latest=[-1]*N
    latest[0]=0
    now=0
    while(K>0):
        K-=1
        to=A[now]
        if latest[A[now]]!=-1:
            K%=latest[now]-latest[A[now]]+1
        latest[A[now]]=latest[now]+1
        now=to
    print(now+1)
        
if __name__=="__main__":
    main()

Solution (Python):
import numpy as np





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

    B = [1]
    s = [True]*(N+1)
    s[1] = False
    nextTown = A[1]
    while s[nextTown]:
        B += nextTown,
        s[nextTown] = False
        nextTown = A[nextTown]
        
    B = np.array(B)
    loopIndex = np.where(B == nextTown)[0][0]
    loopLen = len(B) - loopIndex

    if K >= loopIndex:
        print(B[(K-loopIndex)%loopLen + loopIndex])
    else:
        print(B[K])

main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
vis = [0]*N
p = 1
Town = []

while vis[p-1] == 0:
    Town.append(p)
    vis[p-1] = 1
    p = A[p-1]

l = Town.index(p)

if K < len(Town):
    print(Town[K])
else:
    print(Town[l + (K-l)%(len(Town[l:]))])

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


visited = [0] * N

a = []

town = 1


while visited[town - 1] == 0:
    
    visited[town - 1] = 1
    
    a.append(town)
    
    town = A[town - 1]


loop_head = a.index(town)



if K < len(a):
    print(a[K])
else:
    
    
    K -= loop_head
    print(a[loop_head + K % (len(a) - loop_head)])

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [-1 for _ in range(N)]
visited[0] = 0
k = 0
k = A[k] - 1
count = 0
while visited[k] == -1:
  count += 1
  visited[k] = count
  k = A[k]-1
 
roop = count - visited[k] + 1
beforeroop = visited[k]
 
if K < beforeroop:
  k = 0
  for _ in range(K):
    k = A[k] - 1
  print(k+1)
else:
  K = K - beforeroop
  K = K % roop
 
  for _ in range(K):
    k = A[k]-1
  print(k+1)

Solution (Python):
n,k = map(int,input().split())
alist = list(map(int,input().split()))
memo = []
p = 1
vis = ['.']*n
while vis[p-1] == '.':
    memo.append(p)
    vis[p-1] = 'v'
    p = alist[p-1]

loop = memo.index(p)
if k < len(memo):
    print(memo[k])
else:
    print(memo[loop+(k-loop)%(len(memo)-loop)])

Solution (Python):


import itertools




def main():
    n, k = input_list()
    a = input_list()
    d = {1: 0}
    pre = 1
    loop_start = 0
    loop_end = 0
    loop_pos = 0
    for i in range(1, n+1):
        new = a[pre-1]
        if d.get(new):
            loop_start = d[new]
            loop_end = i
            loop_pos = new
            break
        if i == k:
            print(new)
            exit()
        d[new] = i
        pre = new

    k -= loop_start
    k %= loop_end - loop_start
    pre = loop_pos
    for i in range(k):
        pre = a[pre-1]
    print(pre)

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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Solution (Python):

n,k=list(map(int,input().split()))
m=list(map(int,input().split()))
a=[]
p=1
vis=[0]*n
while vis[p-1]==0:
    a.append(p)
    vis[p-1]=1
    p=m[p-1]

l=a.index(p)

if k<len(a):
    print(a[k])
else:
    k-=l
    print(a[l+k%(len(a)-l)])

Solution (Python):
import sys

input = sys.stdin.readline


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

    route = [0]
    visited = set([0])
    now_town = 0
    while True:
        next_town = A[now_town]
        if next_town in visited:
            break
        else:
            visited.add(next_town)
            route.append(next_town)
            now_town = next_town

    loop_start = route.index(next_town)
    loop_len = len(route[loop_start:])
    count_before_loop = len(route) - loop_len
    if K <= count_before_loop:
        ans = route[K] + 1
    else:
        K -= count_before_loop
        r = K % loop_len
        ans = route[loop_start + r] + 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        self.k_max = K_max.bit_length()
        self.n = len(A)
        self.decrement = decrement
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, self.k_max):
            for j in range(self.n):
                if self.doubling[i - 1][j] != -1:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement





N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Solution (Python):
import sys
input = sys.stdin.readline

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        self.k_max = K_max.bit_length()
        self.n = len(A)
        self.decrement = decrement
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, self.k_max):
            for j in range(self.n):
                if self.doubling[i - 1][j] == -1:
                    self.doubling[i][j] = -1
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement





N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Solution (Python):




"""

全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、
「K個先の要素を求めるのに O(K) かかる」ような状況において

前処理：O(N logK) 時間, O(N logK) 空間
クエリ：O(logK)

で行うことができるようにするアルゴリズム

参考
https://algo-logic.info/doubling/

ベンチマーク
https://atcoder.jp/contests/abc167/submissions/15103640


"""

import sys
input = sys.stdin.readline

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        N = len(A)
        k_max = K_max.bit_length()
        self.N = N
        self.doubling = [[-1] * N for _ in range(k_max + 1)]
        self.decrement = decrement
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, k_max):
            for j in range(N):
                if self.doubling[i - 1][j] == -1:
                    self.doubling[i][j] = -1
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement





N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Solution (Python):
from collections import defaultdict
n, k = map(int, input().split())
a = [0] + [int(i) for i in input().split()]
d = defaultdict(int)
next = 1
for t in range(k):
  if d[next]!=0:
    period = t - d[next]
    res = (k - t)%period
    for _ in range(res):
      next = a[next]
    break
  elif d[next]==0:
    d[next] = t
    next = a[next]
print(next)

Solution (Python):

import sys
input = sys.stdin.readline

class Doubling:
    def __init__(self, A, K_max, decrement=True):
        """
        :param A: リスト。i から A[i] へと移動する
        :param K_max: K_max = 2**(k_max) まで参照する可能性がある
        :param decrement: True = A の要素の decrement が必要
        """
        N = len(A)
        k_max = K_max.bit_length()
        self.N = N
        self.doubling = [[None] * N for _ in range(k_max + 1)]
        self.decrement = decrement
        for i, a in enumerate(A):
            self.doubling[0][i] = a - self.decrement

        for i in range(1, k_max):
            for j in range(N):
                if self.doubling[i - 1][j] is None:
                    self.doubling[i][j] = None
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def apply(self, start, K):
        """
        :param start: スタート地点
        :param K: K回進む
        :return:
        """
        i = start - self.decrement
        for k in range(K.bit_length()):
            m = 1 << k
            if m & K:
                i = self.doubling[k][i]
            if i is None:
                break
        return i + self.decrement





N, K = map(int, input().split())
A = list(map(int, input().split()))
doubling = Doubling(A, 10**18 + 1, decrement=True)
print(doubling.apply(1, K))

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    to = [[None]*n for _ in range(60)]
    to[0] = a[:]
    for i in range(1, 60):
        for j in range(n):
            to[i][j] = to[i-1][to[i-1][j]-1]
    p = 1
    for i in range(59, -1, -1):
        num = 1 << i
        if k >= num:
            k -= num
            p = to[i][p-1]
    print(p)
        

if __name__ == "__main__":
    main()

Solution (Python):
def main():

    n, k = (int(i) for i in input().split())
    tel = [int(i) - 1 for i in input().split()]

    
    slo = tel[0]
    fas = tel[slo]
    k -= 1

    while k != 0 and slo != fas:
        slo = tel[slo]
        fas = tel[tel[fas]]
        k -= 1

    if k == 0:
        print(slo + 1)
        return

    cyc = 0
    while k != 0:
        slo = tel[slo]
        cyc += 1
        k -= 1
        if fas == slo:
            break

    k = k % cyc

    for i in range(k):
        slo = tel[slo]

    print(slo + 1)


main()

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [[0]*N for _ in range(60)]

for i in range(N):
    dp[0][i] = A[i] - 1

for k in range(1, 60):
    for n in range(N):
        dp[k][n] = dp[k - 1][dp[k - 1][n]]

res = []
for i in range(60):
    if (K>>i)&1:
        res.append(i)
    
pos = 0
for i in res:
    pos = dp[i][pos]
print(pos + 1)

Solution (Python):
n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))
 
now = 1
check = [-1]*(n+1)
 
for i in range(k):
  if check[now] == -1:
    check[now] = i
    now = a[now]
  else:
    loop = i - check[now]
    afterloop = (k-(i-loop))%loop
    print(check.index((i-loop) + afterloop))
    exit()
print(now)

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

move = 1
l = [1]
flag = [False]*(N+1)
flag[1] = True

for i in range(K):
    move = A[move-1]
    if flag[move]:
        break
    flag[move] = True
    l.append(move)

ind = l.index(move)
rest = (K-ind) % (len(l) - ind) + ind

print(l[rest])

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

move = 1
l = [1]
flag = [False]*(N+1)
flag[1] = True

for i in range(K):
    move = A[move-1]
    if flag[move]:
        
        
        break
    flag[move] = True
    l.append(move)



ind = l.index(move)

rest = (K-ind) % (len(l) - ind) + ind


print(l[rest])

Solution (Python):

import sys

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


visited_list = [1]
visited_set = set([1])
idx = 0


while True:
    next_idx = A_list[idx] - 1
    
    if (next_idx+1) in visited_set:
        break
    else:
        visited_list.append(next_idx+1)
        visited_set.add(next_idx+1)
        idx = next_idx

    if len(visited_list) == (K+1):
        print(visited_list[K])
        sys.exit()


cycle_start = visited_list.index(next_idx+1)  
cycle_length = len(visited_list) - cycle_start

remain = (K - cycle_start) % cycle_length  
idx = cycle_start + remain

print(visited_list[idx])

Solution (Python):
n, k  = map(int, input().split())
an = list(map(int, input().split()))
bn = [-1]*(n+1)

now=1
bn[1]=0
for i in range(1, k+1):
 
    now = an[now-1]
    if bn[now] >0:
        rp =i-bn[now]
        p= (k-i)%rp
        for j in range(p):
            now = an[now-1]
        print(now)
        exit(0)
    bn[now]=i
print(now)

Solution (Python):
n, k  = map(int, input().split())
an = list(map(int, input().split()))
bn = [-1]*(n+1)

now=1
bn[1]=0
for i in range(1, k+1):
 
    now = an[now-1]
    if bn[now] >0:
        rp =i-bn[now]
        p= (k-i)%rp
        for j in range(p):
            now = an[now-1]
        print(now)
        exit(0)
    bn[now]=i
print(now)

Solution (Python):

from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
tel = deque()
tel.append(1)
visit = [False for _ in range(n)]
visit[0] = True
for i in range(n):
    nx = a[tel[i]-1]
    if visit[nx-1] == True :
        tel.append(nx)
        
        idx = tel.index(nx)
        break
    tel.append(nx)
    visit[nx-1] = True
    


if k <= idx:
    goal = tel[k]
else:
    k -= idx
    loop_num = len(tel) - idx - 1
    
    
    goal = tel[idx + k%loop_num]
    
print(goal)

Solution (Python):



'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

import sys
input = sys.stdin.readline
import marshal

class Graph:
    def __init__(self, n, dictated=False, decrement=True, destroy=False, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.destroy = destroy
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def dfs2(self, info, start, goal=-1, time=0, save=False):
        """
        :param info: 各頂点の付加情報
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: ゴール地点までの距離。存在しなければ -1
        """

        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edge
        else:
            edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    """"""""""""""""""""
                    continue
                if q == goal:
                    """ ゴール時の処理"""
                    
                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                info[q] += info[p]
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """

                """"""""""""""""""""
        return info

    def cycle_detector(self, start, time=0, save=False):
        """
        :param p: スタート地点
        :param save: True = 前回の探索結果を保持する
        :return: 各点までの距離と何番目に発見したかを返す
        """


        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        if self.destroy:
            edge2 = self.edge
        else:
            edge2 = marshal.loads(marshal.dumps(self.edge))

        p, t = start, time
        self.parent[p] = -2
        cycle_end = False
        cycle_time = 0
        cycle = []
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    if not cycle:
                        if q == p:
                            """ 自己ループの時 """
                            cycle.append(q + self.decrement)
                            cycle_end = True
                        else:
                            cycle.append(q + self.decrement)
                            cycle.append(p + self.decrement)
                            cycle_time = t

                    """"""""""""""""""""
                    continue
                """ p から q への引継ぎ"""
                """"""""""""""""""""
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """
                if cycle and t == cycle_time - 1 and not cycle_end:
                    if cycle[0] == p + self.decrement:
                        cycle_end = True
                        continue
                    cycle.append(p + self.decrement)
                    cycle_time = t

                """"""""""""""""""""
        cycle = list(reversed(cycle))
        return [cycle[-1]] + cycle[:-1]

    def tree_counter(self, detail=False):
        """
        :param detail: True = サイクルのリストを返す
        :return: 木（閉路を含まない）の個数を返す
        """
        self.parent = [-1] * self.n

        connection_number = 0
        cycle_list = []

        for p in range(self.n):
            if self.parent[p] == -1:
                connection_number += 1
                cycle = self.cycle_detector(p + self.decrement, save=True)
                if cycle:
                    cycle_list.append(cycle)
        if not detail:
            return connection_number - len(cycle_list)
        else:
            return cycle_list



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

M = N
graph = Graph(N,dictated=True,destroy=True)
for i in range(1,M+1):
    x = i
    y = A[i-1]
    graph.add_edge(x, y)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(graph.cycle_detector(1))
    len_cycle = len(cycle)
    p = 0
    cnt = 0
    res = 0
    while p != cycle[0] - 1:
        p = A[p] - 1
        cnt += 1
    k = (K - cnt) % len_cycle
    res = cycle[k]
print(res)

Solution (Python):




'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
from copy import deepcopy



class Graph:
    def __init__(self, n, dictated=False, decrement=True, edge=[]):
        self.n = n
        self.dictated = dictated
        self.decrement = decrement
        self.edge = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edge:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edge[x].add(y)
        if self.dictated == False:
            self.edge[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edge[i] = set(map(lambda x:x-1, adjacent_list))
        else:
            self.edge[i] = set(adjacent_list)

    def cycle_detector(self, start, time=0, save=False):
        """
        :param p: スタート地点
        :param save: True = 前回の探索結果を保持する
        :return: 各点までの距離と何番目に発見したかを返す
        """

        edge2 = deepcopy(self.edge)

        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n

        p, t = start, time
        self.parent[p] = -2
        cycle_end = False
        cycle_time = 0
        cycle = []
        while True:
            if edge2[p]:
                q = edge2[p].pop()
                if q == self.parent[p] and not self.dictated:
                    """ 逆流した時の処理 """
                    """"""""""""""""""""
                    continue
                if self.parent[q] != -1:
                    """ サイクルで同一点を訪れた時の処理 """
                    if not cycle:
                        if q == p:
                            """ 自己ループの時 """
                            cycle.append(q + self.decrement)
                            cycle_end = True
                        else:
                            cycle.append(q + self.decrement)
                            cycle.append(p + self.decrement)
                            cycle_time = t

                    """"""""""""""""""""
                    continue
                self.parent[q] = p
                p, t = q, t + 1
            else:
                """ 探索完了時の処理 """
                """"""""""""""""""""
                if p == start and t == time:
                    break
                p, t = self.parent[p], t-1
                """ 二度目に訪問時の処理 """
                if cycle and t == cycle_time - 1 and not cycle_end:
                    if cycle[0] == p + self.decrement:
                        cycle_end = True
                        continue
                    cycle.append(p + self.decrement)
                    cycle_time = t

                """"""""""""""""""""
        cycle = list(reversed(cycle))
        return [cycle[-1]] + cycle[:-1]

    def tree_counter(self, detail=False):
        """
        :param detail: True = サイクルのリストを返す
        :return: 木（閉路を含まない）の個数を返す
        """
        self.parent = [-1] * self.n

        connection_number = 0
        cycle_list = []

        for p in range(self.n):
            if self.parent[p] == -1:
                connection_number += 1
                cycle = self.cycle_detector(p + self.decrement, save=True)
                if cycle:
                    cycle_list.append(cycle)
        if not detail:
            return connection_number - len(cycle_list)
        else:
            return cycle_list

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.dictated:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y in self.edge[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        nx.draw_networkx(G)
        plt.show()




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

M = N
graph = Graph(N,dictated=True)
for i in range(1,M+1):
    x = i
    y = A[i-1]
    graph.add_edge(x, y)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(graph.cycle_detector(1))
    len_cycle = len(cycle)
    p = 0
    cnt = 0
    res = 0
    while p != cycle[0] - 1:
        p = A[p] - 1
        cnt += 1
    k = (K - cnt) % len_cycle
    res = cycle[k]
print(res)

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

now = 1
visited = []
visited_set = set()

for i in range(1, K+1):
    visited.append(now)
    visited_set.add(now)
    now = A[now]
    if now in visited_set:
        loop_start = visited.index(now)
        loop_length = i - loop_start
        print(visited[loop_start + (K - loop_start) % loop_length])
        break
else:
    print(now)

Solution (Python):

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

history = [None] * (N+1)

next_town = 1
i = 0
skip_flg = False
while i < K:
  if history[next_town] == None:
    history[next_town] = i
  elif skip_flg == False:
    skip_flg = True
    
    i = i + ((K - i)//(i - history[next_town])) * (i - history[next_town])
  if i < K:
    i += 1
    next_town = A[next_town]
print(next_town)

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

b = [0]*n
r = [0]*n
index = 0
for i in range(1,n+1) :
    if b[a[index]-1] != 0 :
        break
    b[a[index]-1] = i
    index = a[index] - 1

for i in range(1,n+1) :
    if r[a[index]-1] != 0 :
        break
    r[a[index]-1] = i
    index = a[index] - 1

maxb = max(b)
maxr = max(r)
if k <= maxb :
    print(b.index(k)+1)
else :
    k = k - maxb
    if k%maxr == 0 :
        print(r.index(maxr)+1)
    else :
        print(r.index(k%maxr)+1)

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

now = 1
visited = []
visited_set = set()
flag = False

for i in range(1, K+1):
    visited.append(now)
    visited_set.add(now)
    now = A[now]
    if now in visited_set:
        loop_start = visited.index(now)
        loop_length = i - loop_start
        flag = True
        break
else:
    print(now)

if flag:
    print(visited[loop_start + (K - loop_start) % loop_length])

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

now = 1
visited = []
visited_set = set()

for i in range(1, N+1):
    visited.append(now)
    visited_set.add(now)
    now = A[now]
    if now in visited_set:
        loop_start = visited.index(now)
        loop_length = i - loop_start
        break

if K >= loop_start:
    print(visited[loop_start + (K - loop_start) % loop_length])
else:
    print(visited[K])