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
from itertools import chain


def solve(N: int, K: int, A: "List[int]"):
    M = [-1 for _ in range(N)]
    M[0] = 0
    current = 1
    n = 1
    while n <= K:
        current = A[current - 1]
        if M[current - 1] == -1:  
            M[current - 1] = n  
        else:
            loop_len = n - M[current - 1]  
            rest = K - n  
            rest = rest % loop_len  
            K = n + rest
        n += 1
    return current


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    answer = solve(N, K, A)
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    da = [[None]*n for _ in range(64)]
    for i in range(n):
        da[0][i] = a[i]-1
    for i in range(1, 64):
        for j in range(n):
            da[i][j] = da[i-1][da[i-1][j]]
    ans = 0
    for i in range(64):
        p = k&1
        if p == 1:
            ans = da[i][ans]
        k//= 2
    print(ans+1)

if __name__ == "__main__":
    main()

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
point=1
m,l=0,0
if K>N:
    for i in range(N):
        if B[point-1]==0:
            B[point-1]=i+1
            point=A[point-1]
        else:
            m=i+1-B[point-1]
            l=B[point-1]
            break
    if m!=0:
        m=(K-l)%m
    else:
        m=N
else:
    m=K
ans=1
for i in range(l+m):
    ans=A[ans-1]
 
print(ans)

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

dist = [0 for i in [0]*(n+1)]
idx = 1
d = 1
while not dist[idx] and d<k+1:
    dist[idx] = d
    idx = a[idx-1]
    d += 1
    
if d==k+1:
    print(idx)
else:
    rem = dist[idx] - 1
    cyc = d - dist[idx]
    k -= rem
    k %= cyc
    for i in range(k):
        idx = a[idx-1]
    print(idx)

Solution (Python):
n,k = map(int,input().split())
button = list(map(int,input().split()))
visit = [-1]*n
hisitory = [-1]
push = 0
f = 0

for i in range(k):
    visit[push] = i+1
    hisitory.append(push)
    push = button[push] -1
    if(visit[push] != -1):  
        f = 1
        start = visit[push]
        last=push
        end = i+1
        break
if(f == 0):
    print(button[hisitory[-1]])
else:
    geta = start -1
    loopk = k - geta
    loop = end -start + 1
    modk = loopk%loop
    if(modk == 0):
        modk = loop
    print(button[hisitory[geta + modk]])

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

a = [i-1 for i in a]

d = [1]*n
p = 0
b = []
while d[p]:
    b.append(p)
    d[p] = 0
    p = a[p]
avant = b.index(p)
loop_count = len(b) - avant
c = b[avant:]

if k <= avant:
    print(b[k]+1)
else:
    k -= avant
    k %= loop_count
    print(c[k]+1)

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

a = [i-1 for i in a]

d = [1]*n
p = 0
b = []
while d[p]:
    b.append(p)
    d[p] = 0
    p = a[p]
avant = b.index(p)
loop_count = len(b) - avant
c = b[avant:]

if k <= avant:
    print(b[k]+1)
else:
    k -= avant
    k %= loop_count
    print(c[k]+1)

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

visited = [0 for _ in range(N)]
first_visit = [0 for _ in range(N)]

now = 0
flag = True
for i in range(10 ** 5 * 5):
    if first_visit[now] == 0:
        first_visit[now] = i

    visited[A[now] - 1] += 1
    now = A[now] - 1

    if i == K - 1:
        print(now + 1)
        flag = False
        break

if flag:
    num = 0
    for i in range(N):
        if visited[i] > 2:
            num += 1

    for i in range(N):
        if visited[i] >= 2:
            if K % num == first_visit[i] % num:
                print(i + 1)
                break

Solution (Python):
def main():
    n,k=map(int,input().split())
    a=[int(i)-1 for i in input().split()]
    visit=[False]*n
    visit[0]=True
    loop, loopstart, loopout, cur=0, -1, False, 0
    i = 0
    while i < k:
        
        cur=a[cur]
        if not loopout and visit[cur]:
            
            if loopstart == cur:
                k=(k-sum(visit))%loop
                loopout=True
                
                i = 0
                continue
            elif loopstart == -1:
                
                loopstart = cur
            loop+=1
        else:
            visit[cur]=True
        i += 1
    print(cur+1)
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def solve(A, K):
    a = deque() 
    seen = [False for _ in range(len(A))] 
    cur = 0
    while True:
        
        if seen[cur]:
            while a[0] != cur:
                
                K -= 1
                a.popleft()

                
                if K == 0:
                    return a[0] + 1
            break

        
        a.append(cur)
        seen[cur] = True
        cur = A[cur]        
    return a[K % len(a)] + 1

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [v - 1 for v in A]
print(solve(A, K))

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

for i in range(N):
  v[n] = i
  n = A[n]
  if v[n] != -1:
    s = n
    t = i
    l = t - v[s] + 1
    break

if t >= K:
  print(v.index(K))
else:
  K = (K - v[s]) % l
  print(v.index(K + v[s]))

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

v = [-1] * (N + 1)
n = 1
f = 0

for i in range(N):
    v[n] = i
    n = A[n]
    if v[n] != -1:
        f = 1
        s = n 
        t = i
        l = t - v[s] + 1
        break

if t >= K:
    print(v.index(K))
else:
    K = (K - v[s]) % l
    print(v.index(K + v[s]))

Solution (Python):
import sys
from collections import deque

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

visited = set()
q = deque()
q.append(1)

root = []
while q:
    pos = q.pop()
    if pos in visited:
        start = root.index(pos)
        s_len = len(root[:start])
        l_len = len(root[start:])
        break
    visited.add(pos)
    root.append(pos)

    q.append(A[pos-1])

if K <= s_len:
    print(root[K])
else:
    r = (K - s_len) % l_len
    print(root[start+r])

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,K = MI()
A = [0] + LI()

visited = [0]*(N+1)  
times = [0]*(N+1)  
i = 1
a = 0
visited[1] = 0
times[0] = 1
while True:
    i = A[i]
    a += 1
    times[a] = i
    if visited[i] != 0:
        b,c = visited[i],a  
        break
    else:
        visited[i] = a

print(times[K] if K <= a else times[a+(K-a)%(b-a)])

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

dv = []
for _ in range(K.bit_length() + 1):
    l = [0] * N
    dv.append(l)

dv[0] = list(map(lambda x: x-1, As))

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

a = []
for i in range(K.bit_length() + 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 = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
route = [0]
check = {0}
now = 0
while A[now] not in check:
    route.append(A[now])
    check.add(A[now])
    now = A[now]
start = route.index(A[now])
loop = len(route) - start

if K < len(route):
    print(route[K]+1)
else:
    K -= start
    K %= loop
    print(route[start+K]+1)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N,K = MI()
A = [0] + LI()

visited = [0]*(N+1)
times = [0]*(N+1)
i = 1
a = 0
visited[1] = 0
times[0] = 1
while True:
    i = A[i]
    a += 1
    if visited[i] != 0:
        times[a] = i
        b,c = visited[i],a
        break
    else:
        visited[i] = a
        times[a] = i


if K <= a:
    print(times[K])
else:
    print(times[a+(K-a)%(b-a)])

Solution (Python):
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0];BB=[0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    BB.append(nxt)
    now = nxt
  
  print(BB[K]+1)
  exit()
for i in range(N*2):
  nxt = A[now]-1
  
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      B.append(nxt)
      
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
loop_num += 1-loop_cycle

loc = (K-loop_num)%loop_cycle+loop_num


print(B[loc]+1)

Solution (Python):
n,k=map(int,input().split())
a=[-1]+list(map(int,input().split()))
dp=[-1]*(n+1)
now=1
cnt=0
while True:
    nex=a[now]
    cnt+=1
    if dp[nex]!=-1:
        break
    dp[nex]=cnt
    now=nex

loop_start=nex
loop=[loop_start]
loop_now=loop_start
loop_next=-1
while loop_start!=loop_next:
    loop_next=a[loop_now]
    loop.append(loop_next)
    loop_now=loop_next
del loop[-1]
if dp[loop_start]>=k:
    print(dp.index(k))
else:
    d=k-dp[loop_start]
    print(loop[d%len(loop)])

Solution (Python):
from collections import defaultdict

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

A = [int(x) - 1 for x in input().split()]

cur = 0
step = 0
d = defaultdict(int)
d[0] = step
li = []
while True:
    cur = A[cur]
    li.append(cur)
    if d[cur] != 0:
        break
    step += 1
    d[cur] = step

pre = li[:d[cur]]
loop = li[d[cur]:]

if K <= len(pre):
    print(pre[K - 1] + 1)
else:
    K -= len(pre) + 1
    print(loop[K % (len(loop))] + 1)

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

a=[None]+[int(i) for i in input().split()]

circle=[1]
for i in range(n):
    circle.append(a[circle[-1]])

def get_head_double(circle):
    check=[0]*(n+1)
    for i in circle:
        check[i]+=1
    for i in circle:
        if check[i]>=2:
            ans=i
            break
    ans_list=[]
    while len(ans_list)<2:
        for i,j in enumerate(circle):
            if j==ans:
                ans_list.append(i)
    return ans_list

ans_list=get_head_double(circle)
circle_front=circle[:ans_list[0]]
circle_back=circle[ans_list[0]:ans_list[1]]

if len(circle_front)>k:
    print(circle_front[k])
else:
    k=k-len(circle_front)
    print(circle_back[k%len(circle_back)])

Solution (Python):
def resolve():
    N, K = list(map(int, input().split()))
    A = list(map(lambda x: int(x)-1, input().split()))
    routes = [0]
    current = 0
    visited = [False for _ in range(N)]
    visited[0] = True
    while visited[A[current]] is False:
        current = A[current]
        routes.append(current)
        visited[current] = True
    leftlen = routes.index(A[current])
    repeat = routes[leftlen:]
    
    
    
    print(repeat[(K-leftlen)%len(repeat)]+1 if K > leftlen else routes[K]+1)


if '__main__' == __name__:
    resolve()

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[1]
C=["
roop=False
for i in range(K):
    if C[B[i]-1]=="
        C[B[i]-1]="$"
    else:
        roop=True
        break
    B.append(A[B[i]-1])
if roop==True:
    f=B.index(B[i])
    T=i-f
    if T==0:
        print(B[f])
    else:
        r=(K-f)%T
        print(B[f+r])
else:
    print(B[K])

Solution (Python):
from sys import exit
N,K = map(int,input().split())
town = [None]+list(map(int,input().split()))

flag = [None]+[0]*N
remain = K
piece = 1
cnt = 1
while remain > 0:
    if flag[town[piece]] != 0:
        q = cnt-flag[town[piece]]
        piece = town[piece]
        remain -= 1
        break
    else:
        piece = town[piece]
        flag[piece] = cnt
        remain -= 1
        cnt += 1

if remain == 0:
    print(piece)
    exit(0)

remain %= q

while remain > 0:
    piece = town[piece]
    remain -= 1

print(piece)

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

A = [-1] + A

loop_pos = None
loop_start_time = None
loop_end_time = None
visited = [-1]*(N+1)
pos = 1
i = 0
while visited[pos] == -1:
    visited[pos] = i
    pos = A[pos]
    i += 1  
    if visited[pos] != -1:
        loop_pos = pos
        loop_start_time = visited[pos]
        loop_end_time = i


w = loop_end_time - loop_start_time
K = min(K, loop_start_time) + max(0, K-loop_start_time)%w


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

Solution (Python):



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


from fractions import gcd

from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

flag = 0
done = [0] * (N + 1)

root = []
ind = 0

ind = A[0]
root = [1]
done[1] = 1

while True:

    if done[ind]:
        flag = 1
        break
    done[ind] = 1

    root += [ind]
    ind = A[ind-1]

if flag:
    if len(root) <= K:
        left = root.index(ind) - 1
        loopcnt = len(root) - (root.index(ind))

        root2 = root[left+1:]
        print(root2[(K-(left+1)) % loopcnt])
    else:
        print(root[K])
else:
    print(root[K-1])

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

loop = []
mark = ['t'] *n
i = 0
loop.append(1)
mark[0] = 0
while True:
  if mark[lst[i]-1] != 't':
    start = mark[lst[i]-1]
    last = mark[i]
    break
  else:
    mark[lst[i]-1] = mark[i] + 1
    loop.append(lst[i])
  i = lst[i]-1
  
  
loop_len = last - start +1
loop_num = loop[start:last+1]
first = start-1

if k <= first:
  print(loop[k])
else:
  q = (k-first) % loop_len
  print(loop_num[q-1])

Solution (Python):
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
B = [-1 for i in range(N+1)]
B[1] = 0
n = 1
m = 0
while 1:
  n = A[n]
  m += 1
  if m == K:
    print(n)
    break
  if B[n] == -1:
    B[n] = m
  else:
    a = (K - m) % (m - B[n])
    for i in range(a):
      n = A[n]
    print(n)
    break

Solution (Python):
N , K = [int(x) for x in input().split()]
A = [0] + [int(x) for x in input().split()]

orb = [1]
counter = [-1] * (N + 1)
v = A[1]
counter[1] = 0
c = 0
while 1:
    c += 1
    if counter[v] == -1:
        counter[v] = c
        orb.append(v)
        v = A[v]
    else:
        break

L = c - counter[v]
T = counter[v]

if K < c:
    ans = orb[K]
else:
    ans = orb[(K - T) % L + T]

print(ans)

Solution (Python):
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
routes = [0]
visited = [False] * N
visited[0] = True
now = 0
while True:
    next_town = A[now] - 1
    if visited[next_town]:
        routes.append(next_town)
        break
    visited[next_town] = True
    routes.append(next_town)
    now = next_town
for i, r in enumerate(routes):
    if r == routes[-1]:
        loop = copy.deepcopy(routes[i:])
        break
routes.pop()
loop.pop()
if len(routes) > K:
    print(routes[K] + 1)
else:
    K -= len(routes)
    K %= len(loop)
    print(loop[K] + 1)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  N,M=map(int,input().split())
  L=list(map(int,input().split()))
  i=1
  R=list()
  p=set()
  for j in range(N+1):
    if j==M-1:
      print(L[i-1])
      exit()
    if L[i-1] in p:
      c=R.index(L[i-1])
      t=len(R)-c
      m=R[c:]
      break
    R.append(L[i-1])
    p.add(L[i-1])
    i=L[i-1]
  l=(M-c-1)%t
  print(m[l])
if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] 
dsts = set(dst) 
twn = 1 
for _ in range(k):
    if a[twn - 1] in dsts: 
        index = dst.index(a[twn - 1]) 
        ld = len(dst[:index]) 
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
    else: 
        dst.append(a[twn - 1]) 
        dsts.add(a[twn - 1])
        twn = a[twn - 1] 
print(dst[-1])

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

now=0
visited=set()
visited.add((0))
visited2=[0]


while True:
  k-=1
  now=a[now]-1

  if k==0:
    print(now+1)
    exit()

  
  if now in visited:
    visited.add((now))
    visited2.append(now)
    break

  visited.add((now))
  visited2.append(now)


xxx=visited2[-1]
cnt=[]
for i in range(len(visited2)):
  if visited2[i]==xxx:
    cnt.append(i)


k%=cnt[1]-cnt[0]


if k!=0:
  for i in range(k):
    now=a[now]-1
  

print(now+1)

Solution (Python):


import sys






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





















A.insert(0, 0)
cnt = [0] * (N + 1)

j = 1
times_s = 0
times_e = 0
cycle = 0
for i in range(N + 1):
    if i == K:
        print(j)
        sys.exit()
    cnt[j] += 1
    if cnt[j] == 2:
        times_e = i
        cycle = j
        break
    j = A[j]

j = 1
for i in range(N + 1):
    if j == cycle:
        times_s = i
        break
    j = A[j]





K_eff = (K - times_s) % (times_e - times_s)

for i in range(N + 1):
    if i == K_eff:
        print(j)
        sys.exit()
    j = A[j]

Solution (Python):
n, k = map(int,input().split())
a = list(map(int, input().split()))
flg = [True] * n
dst = [1]
twn = 0
for _ in range(k):
    if flg[twn]:
        dst.append(a[twn])
        flg[twn] = False
        twn = a[twn] - 1
    else:
        index = dst.index(a[twn])
        ld = len(dst[:index])
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
print(dst[-1])

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

num = 0
li = [0]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num]
    if flag[num]:
        li.append(num)
        flag[num] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d
print(li[ans]+1)

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

num = 1
li = [1]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num-1]
    if flag[num-1]:
        li.append(num)
        flag[num-1] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d

print(li[ans])

Solution (Python):
def abc167d_teleporter():
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    cnts = [0] * (n + 1)
    i = 1
    nxt = 1
    while True:
        if cnts[a[nxt]] == 0:
            cnts[a[nxt]] = i
        else:
            val = (k - i) // (i - cnts[a[nxt]])
            k -= val * (i - cnts[a[nxt]])
        if i == k:
            break
        i += 1
        nxt = a[nxt]
    print(a[nxt])



abc167d_teleporter()

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
A=[i-1 for i in A]
seen=[-1]*n;seen[0]=0

cnt=0
now=0
roop=[0]
while 1:
    if seen[A[now]]!=-1:
        roopnum=cnt-seen[A[now]]+1
        mae=seen[A[now]]
        trueroop=roop[seen[A[now]]: cnt+1]
        
        break
    now=A[now]
    cnt+=1
    roop.append(now)
    seen[now]=cnt

if k<=mae:
    print(roop[k]+1)
else:
    print(trueroop[(k-mae)%roopnum]+1)

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

visited = [False for _ in range(N)]
visited[0] = True
pattern = [0]
x = 0
start = 0
patternBegin = 0
while True:
    x = A[x]
    if visited[x]:
        patternBegin = x
        break
    pattern.append(x)
    visited[x] = True


patternBeginIndex = pattern.index(patternBegin)
beforeLoop = pattern[0:patternBeginIndex]
repeat = pattern[patternBeginIndex:]


if len(pattern) > K:
    print(pattern[K]+1)
else:
    ans = repeat[(K - len(beforeLoop))%len(repeat)]
    
    print(ans+1)

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

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

    visited = [False] * N
    visited[0] = True

    index = 0
    visited_index = [0]

    while K:
        index = A[index]
        if visited[index]:
            K -= 1
            start = visited_index.index(index)
            loop_index = visited_index[start:]
            print(loop_index[K % len(loop_index)] + 1)
            sys.exit()
        visited_index.append(index)
        visited[index] = True
        K -= 1
    print(index + 1)
    
main()

Solution (Python):
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


_,k = LI()
a = LI()

a = list(map(lambda x:x-1,a))


route = [0]

visited = set([0])
next = a[0]

while True:
    if next in visited:
        loopStart = route.index(next)
        break
    else:
        route.append(next)
        visited.add(next)
        next = a[next]




beforeLoop = route[:loopStart]

loop = route[loopStart:]



if k < loopStart:
    ans = beforeLoop[k]

else:
    numOfLoops,mod = divmod((k-(loopStart)),len(loop))
    
    ans = loop[mod]

ans += 1
print(ans)

Solution (Python):
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


_,k = LI()
a = LI()

a = list(map(lambda x:x-1,a))


route = [0]

visited = set([0])
next = a[0]

while True:
    if next in visited:
        loopStart = route.index(next)
        break
    else:
        route.append(next)
        visited.add(next)
        next = a[next]




beforeLoop = route[:loopStart]

loop = route[loopStart:]



if k < loopStart:
    ans = beforeLoop[k]

else:
    numOfLoops,mod = divmod((k-(loopStart)),len(loop))
    
    ans = loop[mod]

ans += 1
print(ans)

Solution (Python):
n, K = map(int, input().split())
A = [x-1 for x in list(map(int, input().split()))]

current = 0
d = dict()
d[current] = d.get(current, 0) + 1
pattern = [0]
cnt = K

while True:
    current = A[current]
    if d.get(current) == 2:
        break
    else:
        if d.get(current) == None:
            d[current] = d.get(current, 0) + 1
        else:
            d[current] = d.get(current) + 1
        pattern.append(current)
        cnt -= 1
        if cnt == 0:
            break

if cnt == 0:
    print(pattern[-1]+1)
else:
    loop = len([key for key, value in d.items() if value == 2])
    not_loop = len([key for key, value in d.items() if value != 2])
    pattern = pattern[not_loop:]
    ans_position = (K - not_loop) % loop

    print(pattern[ans_position]+1)

Solution (Python):

import sys
n,k = map(int,input().split())
a_ls = list(map(int, input().split()))
for i in range(n):
    a_ls[i] -= 1
town_done = [0] * n


now_town = 0
times = 0
while True:
    
    town_done[now_town] = 1
    
    
    now_town = a_ls[now_town]
    times += 1
    if times == k:
        print(now_town+1)
        sys.exit()
    if town_done[now_town]:
        base = now_town
        break

rest = k - times
times = 0
while True:
    now_town = a_ls[now_town]
    times += 1
    rest -= 1
    if now_town == base:
        times_per_loop = times
        break
    if rest == 0:
        print(now_town+1)
        sys.exit()

rest = rest % times_per_loop
for _ in range(rest):
    now_town = a_ls[now_town]
print(now_town+1)

Solution (Python):
n, k = map(int, input().split())
arr = list(map(int, input().split()))
l = [-1]*(n+1)  
tmp = []  
pos = 1  
cnt = 0  
while 1:
    if l[pos] != -1:  
        t = cnt-l[pos]  
        if k < cnt:
            print(tmp[k])
        else:  
            print(tmp[l[pos]+(k-cnt) % t])
        break
    l[pos] = cnt
    cnt += 1
    tmp.append(pos)
    pos = arr[pos-1]

Solution (Python):

def main():
    N, K = map(int, input().split())
    A = [int(x) - 1 for x in input().split()]

    way = []
    seen = [False for _ in [0] * (2 * 10 ** 5 + 1)]
    now = 0
    for _ in range(K):
        if seen[now]:
            loop_start = way.index(now)
            loop = way[loop_start:]
            K -= len(way[:loop_start])
            now = loop[K % len(loop)]
            break
        way.append(now)
        seen[now] = True
        now = A[now]
    print(now + 1)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
i=l=1
l=0
F=[0]*n
L=[]
while 1:
  i=A[i-1]
  if F[i-1]>0:
    break
  else:
    L.append(i)
    F[i-1]=l
    l+=1
print((L[F[i-1]:])[(k-F[i-1])%(l-F[i-1])-1] if k>F[i-1] else L[k-1])

Solution (Python):
"TLE"

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

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

A_dir_list = []
A_visit_list = [-1 for i in range(N)]
dir = 0

while True:
    A_dir_list.append(dir)
    A_visit_list[dir] = 1
    if A_visit_list[A_list[dir]-1] == -1: 
        dir = A_list[dir]-1
    else:
        cycle_pos = A_dir_list.index(A_list[dir]-1)
        break

if K < cycle_pos:
    print(A_dir_list[K]+1)

else:
    cnt = (K-cycle_pos)%(len(A_dir_list)-cycle_pos)
    print(A_dir_list[cnt+cycle_pos]+1)

Solution (Python):
import math

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


dv = []
for _ in range(int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)


dv[0] = [a-1 for a in A]


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 = map(int, input().split())
A = list(map(int, input().split()))

A.insert(0,0)

start = 1
next_ = A[1]

visited = [0] * (N+1)
visited[start] = 1

route = [1]
cnt = 0
while True:
    if visited[next_] == 1:
        break
    visited[next_] = 1
    route.append(next_)
    cnt += 1
    if cnt >= K:
        print(next_)
        exit()
    next_ = A[next_]

roop_s = route.index(next_)
roop = route[roop_s:]

stop = (K - roop_s) % len(roop) + 1
ans = roop[stop-1]

print(ans)

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

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

l=[1]
di={}
di[1]=1

for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1

t2=len(l)-t1
if k<=t1:
    print(l[k])

else:
    aa=(k-t1)%t2
    print(l[t1+aa])

Solution (Python):
_, k = map(int, input().split())
a = list(map(int, input().split()))
d = {1: 0}

k += 1
next = 1
cnt = 1
flg = True
while cnt < k:
    next = a[next - 1]
    if flg and next in d:
        flg = False
        d_next = d[next]
        loop_cnt = cnt - d_next  
        k -= ((k - d_next) // loop_cnt - 2) * loop_cnt
    d[next] = cnt
    cnt += 1
print(next)

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
point=1
m,l=0,0
if K>N:
    for i in range(N):
        if B[point-1]==0:
            B[point-1]=i+1
            point=A[point-1]
        else:
            m=i+1-B[point-1]
            l=B[point-1]
            break
    if m!=0:
        m=(K-l)%m
    else:
        m=N
else:
    m=K
ans=1
for i in range(l+m):
    ans=A[ans-1]

print(ans)

Solution (Python):
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = [0];BB=[0]
S = set([]);S.add(0)
now = 0
Flag = False
loop_start = -1
if K <= 2*pow(10,5)+10:
  for i in range(K):
    nxt = A[now]-1
    BB.append(nxt)
    now = nxt
  
  print(BB[K]+1)
  exit()
for i in range(N*2):
  nxt = A[now]-1
  
  if nxt in S:
    if Flag:
      if nxt == loop_start:
        
        loop_cycle = i-loop_num
        break
    else:
      loop_start = nxt
      loop_num = i
      B.append(nxt)
      
      Flag = True
  else:
    B.append(nxt);S.add(nxt)
  now = nxt
loop_num += 1-loop_cycle

loc = (K-loop_num)%loop_cycle+loop_num


print(B[loc]+1)

Solution (Python):
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)