Problem:


Score: 400 points

Problem Statement

The Kingdom of Takahashi has N towns, numbered 1 through N.

There is one teleporter in each town. The teleporter in Town i (1 \leq i \leq N) sends you to Town A_i.

Takahashi, the king, loves the positive integer K. The selfish king wonders what town he will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Help the king by writing a program that answers this question.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

1 \leq K \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the integer representing the town the king will be in if he starts at Town 1 and uses a teleporter exactly K times from there.

Sample Input 1

4 5
3 2 4 1

Sample Output 1

4

If we start at Town 1 and use the teleporter 5 times, our travel will be as follows: 1 \to 3 \to 4 \to 1 \to 3 \to 4.

Sample Input 2

6 727202214173249351
6 5 2 5 3 2

Sample Output 2

2



Sample input:
4 5
3 2 4 1


Sample output:
4

Submission status: Accepted

Solution code:
# abc167_d.py
N, K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
flg = [0] * N
route = [0]
is_ok = 0
while K > 0:
    K-=1
    if flg[pos] == 1 and is_ok==0:
        route = route[route.index(A[pos] - 1):]
        K%=len(route)
        is_ok = 1
#        print("find cycle!:",route)
    flg[pos] = 1
    pos = A[pos] - 1
    route.append(pos)
#    print(route)
print(pos + 1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split(' '))
A=list(map(lambda x:int(x)-1,input().split(' ')))
roop=[0]
flg = [0 for i in range(N)]
flg[0]=1
n = A[0]
for i in range(2,N+1):
    if flg[n]==0:
        roop.append(n)
        flg[n] = i
        n = A[n]
    else:
        end=i
        break
if K <len(roop):
    print(roop[K]+1)
else:
    K-=flg[n]-1
    K%=(end-flg[n])
    roop=roop[flg[n]-1:end]
    print(roop[K]+1)

Submission status: Accepted

Solution code:
#D

#デバッグ
debug=1
def pront(*n):
    if debug==1:
        print(n)
        
#10**9+7を底とした処理

base=10**9+7

def add(a,b):#a+b
    return (a+b)%base

def sub(a,b):#a-b
    return (a-b)%base

def multi(a,b):#a*b
    return (a*b)%base

def exp(a,b):#a**b
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

def div(a,b):#a/b
    return(multi(a,exp(b,base-2)))

#入力
N,K=map(int,input().split())

A=list(map(int,input().split()))
B=[0 for i in range(len(A))]
#処理
x=[]
y={}
i=0
j=1
while True:
    if B[i]!=0:
        p=B[i]
        break
    else:
        B[i]=j
        x.append(A[i])
    i=A[i]-1
    j+=1

T=len(x)-p+1

if K<=p:
    print(x[K-1])
else:
    print(x[((K-p+1)%T)+p-2])

#print(x,B,K,p,((K-p+1)%T)+p-2)

Submission status: Accepted

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

group = [0]
now = 0
seen = [0]*n
seen[0] = 1
while True:
    now = an[now] - 1
    
    group.append(now)
    if seen[now] == 1:
        break
    seen[now] = 1

l = len(group)
a = group.index(group[-1])
roop = l - a - 1
if k < a:
    print(group[k] + 1)
else:
    x = (k - a) % roop
    print(group[a + x] + 1)

Submission status: Accepted

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

cnt = [0]*N
town = 1
for i in range(K):
    if cnt[town-1] ==1:
        break

    cnt[town-1] += 1
    town = A[town-1]


ans1 = sum(cnt)

import copy
town2 = copy.deepcopy(town)

cnt2 = [0]*N

for i in range(K):
    if cnt2[town2-1] ==1:
        break

    cnt2[town2-1] += 1
    town2 = A[town2-1]
    
ans2 = sum(cnt2)

if K <= 10**8:
    town4 = 1
    for i in range(K):
        town4 = A[town4-1]
    print(town4)
else:
    town3 = 1
    cnt3=[0]*N
    K2 = ((K-(ans1-ans2))%(ans2))+(ans1-ans2)
    for i in range(K2):
        if cnt3[town3-1] ==1:
            break

        cnt[town3-1] += 1
        town3 = A[town3-1]
    print(town3)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
B=[0]*(N+1)
counter=1
looper=0
start=0
loopf=0
now=1
A=[0]+A
if N>K:
    for i in range(0,K):
        now=A[now]
    print(now)
    exit()

while True:
    if B[now]==0:
        B[now]=counter
        counter+=1
        now=A[now]
    else:
        start=B[now]
        loopf=now
        looper=counter-start
        break
K=K+1-start
K=K%looper
for i in range(0,K):
    loopf=A[loopf]
print(loopf)

Submission status: Accepted

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

flg = True
c = [0 for i in range(n)]
i = 1
b = []
d = []
one = False
while flg:
	x = i-1
	if c[x] == 1 and a[x] == 1:
		flg = False
		one = True
		break
	elif c[x] == 3:
		flg = False
		break
	else:
		c[x] += 1
		if c[x] == 1:
			b.append(x+1)
		if c[x] == 2:
			d.append(x+1)
	i = a[x]
y = k % len(b)
ans = b[y]
if k < len(b):
	print (ans)
else:
	if one:
		print (ans)
	else:
		k -= len(b)
		y = k % len(d)
		ans = d[y]
		print (ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [-1] + list(map(int,input().split()))
if k < 2*10**5:
    now = 1
    for _ in range(k):
        now = a[now]
    print(now)
    exit()

ispass = [False]*n
now = 1
loop = set()
loop_first = -1
for _ in range(2*n):
    if ispass[now-1] == False:
        ispass[now-1] = True
    else:
        if loop_first == -1:
            loop_first = now
        loop.add(now)
    now = a[now]

k = k - (ispass.count(1) - len(loop))
k = k % len(loop)

now = loop_first
for _ in range(k):
    now = a[now]
print(now)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K = LI()
A = LI()

visited = [-1]*N
s = 0
visited[s] = 0
count = 1
while True:
    x = A[s]-1
    if visited[x] < 0:
        visited[x] = count
        s = x
        count += 1
    else:
        break

r = count-visited[x]
y = visited[x]

if K >= y:
    k = (K-y)%r
    s = x
    for i in range(k):
        s = A[s]-1
    print(s+1)
else:
    s = 0
    for i in range(K):
        s = A[s]-1
    print(s+1)

Submission status: Accepted

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

def solve():
    visited = [-1]*N
    visited[0] = 0
    goto = 1
    counter = 0
    period = 0
    while 1:
        counter += 1 #counter 回ワープした
        goto = A[goto-1] #counter回目につく場所

        if counter == K:
            print(goto)
            return 0

        if visited[goto-1] == -1:
            visited[goto-1] = counter
        else:
            period = counter - visited[goto-1]
            break

    
    warp = 0
    here = 1
    while here != goto:
        warp += 1
        here = A[here-1]

    peri_and_rem = K - warp
    rem = peri_and_rem % period

    while rem > 0:
        rem -= 1
        here = A[here - 1]


    print(here)
    return 0
        



solve()

Submission status: Accepted

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

visit_check = [0 for i in range(len(a))]

pos=0
root = []
while(1):
    if visit_check[pos]==0:
        visit_check[pos]=1
        root.append(pos)
    else:
        loop_index = root.index(pos)
        if loop_index==0:
            root_one = []
            root_loop = root
        else:
            root_one = root[:loop_index]
            root_loop = root[loop_index:]
        break
    pos = a[pos]-1

if k+1<=len(root_one):
    ans = root_one[k]+1
else:
    k = k-len(root_one)
    index = k%len(root_loop)
    ans = root_loop[index]+1
# print(root_one)
# print(root_loop)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    town = [-1] * N
    town[0] = 0
    next = A[0]
    roop = -1
    until_roop = -1

    for i in range(1, N+1, 1):
        if(i == K):
            print(next)
            return
        if(town[next-1] == -1):
            town[next-1] = i
            next = A[next-1]
        else:
            roop = i - town[next-1]
            until_roop = town[next-1]
            roop_start = next
            break

    mod = (K - until_roop) % roop
    index = roop_start
    while(mod>=0):
        if(mod == 0):
            print(index)
            break
        else:
            index = A[index-1]
            mod -= 1

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
arr = []
check = [0] * (n + 2)
check[1] = 1
c = 0
num = 1
yo = 0
while 1:
    arr.append(l[c])
    if l[c] == 1:
        yo = 1
        break
    if check[l[c]]:
        arr.pop()
        c = l[c]
        break
    check[l[c]] = 1
    num -= -1
    c = l[c] - 1
# print(arr, c)
for i in range(len(arr)):
    if arr[i] == c:
        c = i + 1
        break
# print(c)
if yo == 1:
    print(arr[k % len(arr) - 1])
elif k < c: print(arr[k - 1])
else:
    ne = arr[c - 1: ]
    k = k - (c - 1)
    print(ne[k % len(ne) - 1])

Submission status: Accepted

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

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

C = [1]
D = {1}
i = 0
C1 = []
C2 = []
while True:
    if A[i] not in D:
        C.append(A[i])
        D.add(A[i])
        i = A[i]-1
    else:
        index = C.index(A[i])
        C1 = C[:index]
        C2 = C[index:]
        break

        
if K <= len(C1)-1:
    print(C1[K])
else:
    r = (K-len(C1))%len(C2)
    print(C2[r])

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]
flag = [False]*N
l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    flag[place]=True
    place = A[place]
    K -= 1
    if flag[place]:
        ind = l.index(place)
        count = len(l) - ind
        print(l[ind + K%count]+1)
        exit()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
p=1
l=[0]*n
#l[0]+=1
if k<=200000:
    for i in range(k):
        p=A[p-1]
        l[p-1]+=1
    print(p)
    exit()
else:
    for i in range(200001):
        p=A[p-1]#A[0]の番号の町に飛ぶ
        l[p-1]+=1
        #print(p)
        if l[p-1]==2:
            x=i
            break
    #print("p=",str(p))
    #print(l,x)

    d=1
    for j in range(200001):
        d=A[d-1]#A[0]の番号の町に飛ぶ
        if d==p:
            y=j
            break
    #print("y=",str(y))
    z=(k-x-1)%(x-y)#yから数えて残り回す回数
    #print(z)
    for i in range(z):
        p=A[p-1]
        #print(p)
    print(p)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

city = 1
p = [0]*n
p[0] = 1
root = [1]

for cnt in range(k):
    city = a[city-1]
    root.append(city)
    if p[city-1] == 1:
        break
    else:
        p[city-1] = 1
    if cnt == k-1:
        print(city)
        exit()
        
loop = root[root.index(city):-1]

num = (k - root.index(city))%(len(loop))
print(loop[num])

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())
a = [None] + a
done = [None] + [0] * n
t = 0
p = 1
while not done[p]:
    done[p] = t
    p = a[p]
    t += 1

loop = t - done[p]
orig = done[p]

if k - orig > 0:
    k = (k - orig) % loop + orig
p = 1
while k:
    p = a[p]
    k -= 1

print(p)

Submission status: Accepted

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

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

check = [0] * n

start = 0
path = []
for i in range(n):
    if check[start] == 0:
        check[start] = 1
        path.append(start)
        start = A[start] - 1
path.append(start)

before_roop = path[:path.index(path[-1])]
B = before_roop
if before_roop == []:
    before_roop = 0
else:
    before_roop = len(before_roop)

roop = len(path) - before_roop - 1

if k <= before_roop:
    print(path[:before_roop+1][k] + 1)
else:
    k -= before_roop
    k = k % roop
    print(path[before_roop+1:][k-1] + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))
    perm = [1]
    seen = [[-1, False] for _ in range(N+1)]
    seen[1] = [1,True]
    l = 1
    while True:
        v = perm[-1]
        idx, boo = seen[A[v]]
        if boo: break
        l += 1
        perm.append(A[v])
        seen[A[v]] = [l,True]

    if K <= idx -1:
        print(perm[K])
        return None
    K -= idx - 1
    perm = perm[idx-1:]
    print(perm[K % len(perm)])

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
V=[0]*n
V[0]=0
a=0
c=0
for i in range(k):
  a=A[a]-1
  if V[a]!=0:
    break
  V[a]=i+1
if i==k-1:
  print(a+1)
  exit()
else:
  k=(k-V[a])%(i+1-V[a])
  for i in range(k):
    a=A[a]-1
  if k==0:
    print(a+1)
  else:
    print(a+1)

Submission status: Accepted

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

V = [-1] * N
V[0] = 0
H = [0]
for i in range(1, K + 1):
    n = A[H[i - 1]]
    H.append(n)
    if V[n] != -1:
        start_L = V[n]
        L = H[start_L:i]
        break
    V[n] = i

if len(H) == K + 1:
    ans = H[K]
else:
    t = len(L)
    ans = L[(K - start_L) % t]
print(ans + 1)

Submission status: Accepted

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


def main(input, print):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    visited = [False] * n
    route = [-1] * n
    now = 0
    start = -1
    for i in range(k):
        if visited[now]:
            for j in reversed(range(i)):
                if route[j] == now:
                    start = j
                    break
            loop = i-j
            pos = (k-start) % loop
            print(route[start+pos]+1)
            return

        route[i] = now
        visited[now] = True
        now = a[now]-1

    print(now+1)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
T = [1]
TN = 1
for i in range(min(N,K)):
    T.append(A[TN-1])
    TN = T[-1]
if min(N,K) ==K:
    print(TN)
else:
    R1 = T[-1]
    R2 = T[-1]
    T2 = [T[-1]]
    for i in range(N):
        if R2 != A[R1-1]:
            T2.append(A[R1-1])
            R1 = T2[-1]
        else:
            break
    K = K - N
    Kmod = K%len(T2)
    print(T2[Kmod])

Submission status: Accepted

Solution code:
import sys

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

array = [-1] * (n+1)
array[1] = 0

li = []
li.append(1)

tmp = -1
index = 0
for i in range(2 * (10**5)):
  if array[a[index]] != -1:
    tmp = array[a[index]]
    break
    
  if i == k:
    print(index+1)
    sys.exit(0)
    
  li.append(a[index])
  array[a[index]] = i+1
  index = a[index] -1
  
k -= tmp
d = len(li) - tmp

k %= d

print(li[k+tmp])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N,K = map(int,sys.stdin.readline().split())
A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param

d = {}
a = []
n = 1
i = 0
while True:
    #print(n)
    d[n] = i
    i += 1
    a.append(n)
    n = A[n-1]
    if n in d:
        break
pre = d[n]
cycle = a[pre:]
#print(pre,a,cycle)
if K < pre:
    print(a[K])
else:
    print(a[pre+(K-pre)%(len(cycle))])

Submission status: Accepted

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

visited = [0]*n
route=[0]
stack=[a_input[0]]

def dfs(visited,route,stack,k):
    while True:
        x = stack.pop(0)
        k-=1
        if k==0:
            print(x+1);exit()
            break
        if visited[x]==1:
            break
        stack.append(a_input[x])
        route.append(x)
        visited[x]=1
    return route,x,k+1

route,x,k = dfs(visited,route,stack,k)
loop = route[route.index(x):]

print(loop[k%len(loop)-1]+1)

Submission status: Accepted

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

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

visited = [-1] * (n + 1)

next = 1
cnt = 0
while cnt < k:
    if visited[next] == -1:
        visited[next] = cnt
        cnt += 1
    else:
        mod = cnt - visited[next]
        break
    next = a[next - 1]

if cnt == k:
    print(next)
    exit(0)

k -= cnt
k %= mod

for i in range(k):
    next = a[next - 1]

print(next)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = list(map(int,input().split()))
L = [1]
La = [0] * n
La[0] = 1
tmp = a[0]
while True:
    L.append(tmp)
    if La[tmp-1] == 0:
        La[tmp-1] = 1
        tmp = a[tmp-1]
    else:        
        break
po = L.index(L[-1])
base = len(L) - po - 1
if po > m:
    ans = m
else:
    ans = (m - po) % base + L.index(L[-1])

print(L[ans])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
used = [True] * n
used[0] = False
i = a[0]
k1 = 1
g = [0]
f1 = True
while True:
    if k == k1:
        f1 = False
        print(i + 1)
        break
    if used[i]:
        used[i] = False
        k1 += 1
        g.append(i)
        i = a[i]
    else:
        break
if f1:
    f = False
    g1 = []
    for j in g:
        if j == i:
            f = True
        if f:
            g1.append(j)
    print(g1[(k - (len(g) - len(g1))) % len(g1)] + 1)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
tl=[-1]*n
tl[0]=0
index=0
i=1
while True:
  index=l[index]-1
  if k==i:
    break
  elif tl[index]==-1:
    tl[index]=i
  else:
    last=(k-tl[index])%(i-tl[index])
    for i in range(last):
      index=l[index]-1
    break
  i=i+1
print(index+1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

graph = defaultdict(list)
g = defaultdict(list)
E = [[] for i in range(N)]
visited = [False] * N
for i, a in enumerate(A):
    graph[i].append((a-1, 1))
    g[i].append(a-1)
q = deque([0])
# ma = 0
order = []
while q:
    a = q.popleft()
    if visited[a] == True:
        last_idx = a
        break
    visited[a] = True
    order.append(a)

    for node in g[a]:
        q.append(node)

for i, a in enumerate(order):
    if a == last_idx:
        order_idx = i
# print(order_idx)
if K < order_idx:
    print(order[K]+1)
else:
    order_syuki = order[order_idx:]
    len_syuki = len(order_syuki)
    saigo_num = K - order_idx
    i_in_here = saigo_num % len_syuki
    ans = order_syuki[i_in_here]
    print(ans+1)


# if K <= 

# ma_d = ma - d[last_idx]
# mi_d = d[last_idx]
# print(ma_d, mi_d)

Submission status: Accepted

Solution code:
# Contest No.: ABC167
# Problem No.: D
# Solver:      JEMINI
# Date:        20200510

import sys

def main():
    n, k = map(int, sys.stdin.readline().split())
    nums = [None]
    nums += list(map(int, sys.stdin.readline().split()))
    visited = [1]
    visitedSet = set([1])
    temp = nums[1]
    cnt = 0
    while temp not in visitedSet:
        if cnt == k:
            break
        visited.append(temp)
        visitedSet.add(temp)
        temp = nums[temp]
        cnt += 1
    if len(visited) > k:
        print(visited[-1])
        return
    frontCnt = visited.index(temp)
    k -= frontCnt
    cnt = k % (len(visited) - frontCnt)
    print(visited[frontCnt + cnt])
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = [int(x) for x in input().split()]
a_list = [0] + [int(x) for x in input().split()]

ci = 1
temp_dict = {1: 0}
temp_list = [1]
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)

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
#x = int(input())
n, k = map(int, sys.stdin.readline().split())
#s = input()
a = list(map(int, sys.stdin.readline().split()))

q = [0 for i in range(n)]
l = [1]
i = 0
while (True):
    if q[a[l[i]-1]-1] == 1:
        p = l.index(a[l[i]-1])
        break
    
    q[a[l[i]-1]-1] = 1
    l.append(a[l[i]-1])
    i += 1

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

Submission status: Accepted

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7

n, k = read_n_item()
teleporter = [0] + read_n_item()

pos = 1
cycle = []
visited = [False] * (n+1)

for _ in range(k):
    cycle.append(pos)
    visited[pos] = True
    pos = teleporter[pos]
    if visited[pos]:
        break

if not visited[pos]:
    print(pos)
else:
    start = cycle.index(pos)
    cycle_len = len(cycle) - start
    end = (k - start) % cycle_len
    print(cycle[start + end])

Submission status: Accepted

Solution code:
n, k, *A = map(int, open(0).read().split())
B = set()
C = []
p = 0
while True:
    p = A[p]-1
    if p in B:
        C.append(p)
        break
    B.add(p)
    C.append(p)

x = C.index(p)
if k-1 < x:
     print(C[k-1]+1)
else:
    D = C[x:len(C)-1]
    print(D[(k-1-x) % len(D)]+1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque

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

loop = N
pos = 0
oto = defaultdict(int)
ind = 0
tej = deque([])
for i in range(N):
    pos = A[pos] - 1
    tej.append(pos+1)
    if oto[pos] == 1:
        ind = tej.index(pos+1)
        loop = i - ind 
        break
    oto[pos] = 1
K -= 1
##print("loop",loop,"ind",ind)
##print(tej)
if K <= ind:
    print(tej[K])
else:
    print(tej[(K-ind)%loop+ind])

Submission status: Accepted

Solution code:
from collections import deque

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

for i,l in enumerate(li):
  li[i]-=1

done = [0]*n
root = []
que  = deque()

done[0] = 1
root.append(0)
que.append(li[0])


while(len(que)!=0 and len(root)<k+1):
  v = que.pop()
  
  if done[v]!=0:
    root.append(v)
    break

  done[v] = 1
  root.append(v)
  que.append(li[v])

if len(root)==k+1:
  print(root[-1]+1)
else:
  fidx = root.index(root[-1])
  lidx = len(root)-1
  lp   = lidx-fidx

  cnt = (k-fidx)%lp

  if cnt==0:
    print(root[-1]+1)
  else:
    que.append(root[-1])
    for i in range(cnt):
      v = que.pop()
      que.append(li[v])
    print(que.pop()+1)

Submission status: Accepted

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

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

b = [0]*n
pos = 0

j = 0

while True:
	b[pos] += 1
	if b[pos]>1:
		rpos = pos
		pos = a[rpos]-1
		i = 1
		while True:
			if pos == rpos:
				break
			pos = a[pos]-1
			i += 1
		break
	
	pos = a[pos]-1
	j += 1

j = j-i

if k>j:
	kp = (k-j)%i
	pos = rpos
else:
	kp = k
	pos = 0

for _ in range(kp):
	pos = a[pos]-1

print(pos+1)

Submission status: Accepted

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

went_town = set()
now = 1
turn_town = [0]
while True:
    if now-1 in went_town:
        break
    else:
        went_town.add(now-1)
        now = A[now-1]
        turn_town.append(now-1)

for i in range(len(turn_town)-1):
    if turn_town[i] == turn_town[-1]:
        roop_index = i

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
visited = [0]*(n+1)
pos = 1
steps = 0
while visited[pos] == 0:
	visited[pos] = steps
	steps += 1
	pos = a[pos]
#print(visited)
if k>=steps:
	k -= visited[pos]
	k %= (steps-visited[pos])
	#print(k)
	for i in range(1,n+1):
		if visited[i] == visited[pos]+k:
			print(i)
			break
else:
	for i in range(1,n+1):
		if visited[i] == k:
			print(i)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
4 5
3 2 4 1
'''

def solve(l,k):
	n = len(l)
	curr = 0
	zz = 1
	done = defaultdict(int)
	last = 1
	prev = 0
	done[curr+1] = zz
	f = 0
	while(zz <= k):
		last = curr + 1
		curr = l[curr]-1
		zz += 1
		if(done[curr+1] != 0):
			f = 1
			last = curr+1
			break
		else:
			done[curr+1] = zz
	if(len(done) == 1):
		return l[0]
	zz -= 1
	if(zz == 1):
		return l[0]
	mod = k%zz
	k = k - done[last] + 1
	cycle = zz - done[last] + 1
	mod = k%cycle
	find = mod+done[last]
	if(not f):
		return curr + 1
	for i in done:
		if(done[i] == find):
			return i
	return curr+1
	

N,K = list(map(int, stdin.readline().rstrip().split()))
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l,K)
print(ans)

Submission status: Accepted

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

start=1
list=[1]
kenti=[0 for i in range(n)]
kenti[0]=1

zan=-1

for i in range(k):
  start-=1
  next=a[start]
  start=next

  if kenti[start-1]!=0:
    zan=k-(i+1)
    inx=list.index(start)
    list=list[inx:]
    break
  else:
    list.append(start)
    kenti[start-1]+=1

if zan==-1:
  print(list[-1])
  exit()
elif zan==0:
  print(list[0])
  exit()

#zan-=1
#print(list,zan)
zan%=len(list)
#print(zan)
'''
if zan==0:
  print(list[-1])
else:
  print(list[zan])
'''
print(list[zan])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(i)-1 for i in input().split()]
l = []
d = {}
p = 0
while p not in d:
    d[p] = len(l)
    l.append(p)
    p = A[p]
if K < len(l):
    print(l[K % len(l)] + 1)
    exit()
elif K == len(l):
    print(p + 1)
    exit()
K -= d[p]
K %= len(l) - d[p]
print(l[K + d[p]] + 1)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
telport_from = {source: to for source, to in zip(range(1, n+1), map(int, input().split()))}

trajectory = [1]
visited = set((1,))
current = 1
has_loop = False
for _ in range(k):
  next_city = telport_from[current]

  trajectory.append(next_city)
  if next_city in visited:
    has_loop = True
    break
  current = next_city
  visited.add(current)

if not has_loop:
  print(next_city)
else:
  loop_start = trajectory.index(next_city)
  loop_length = (len(trajectory)) - loop_start - 1
  remain_step = (k - loop_start) % loop_length
  #print(trajectory)
  
  #print(f'{loop_start=} {loop_length=} {remain_step=}')
  # fix index
  last_city = trajectory[loop_start+remain_step]
  print(last_city)

Submission status: Accepted

Solution code:
def findKey(C, x):
    for i, c in enumerate(C):
        if c == x:
            return i

    return None
    

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

C = [None]*(N)

p = 1
c = 0
C[p-1] = c

while True:
    p = A[p-1]
    c += 1

    if C[p-1] != None:
        break

    C[p-1] = c

start = C[p-1]
cycle = c - start

# print(C,c1, c2)

if K <= start:
    print(findKey(C, K)+1)
else:
    print(findKey(C, (K-start)%cycle+start)+1)

Submission status: Accepted

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

steps = 0
cur = 1
visited = [-1] * (n+1)
while k:
    if visited[cur] != -1:
        k = k % (steps - visited[cur])
        break
    visited[cur] = steps
    cur = a[cur]
    k -= 1
    steps += 1

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

else:
    print(cur)