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: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
visit = [-1 for i in range(n)]
root = []
now = 1
length = 0
root.append(now)
if k > 10**6:
    for i in range(n):
        if visit[now - 1] != 1:
            visit[now - 1] = 1
            now = a[now - 1]
            root.append(now)
            length += 1
        else:break
    start = 0
    for i in range(n):
        if root[i] == now:
            start = i
            break
    length -= start
    k -= start
    k %= length
    ans = root[start]
    for i in range(k):
        ans = root[start + i]
    print(ans)
else:
    for i in range(k):
        now = a[now - 1]
    print(now)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
tele=[0 for _ in range(n+1)]
cnt=1
v=1
while True:
    if tele[v]!=0:
        break
    else:
        tele[v]=cnt
        cnt+=1
        v=A[v-1]

circle_in=tele[v]
circle=[]
for idx,t in enumerate(tele):
    if t<circle_in:
        continue
    else:
        circle.append((t,idx))
circle.sort()

circle_len=len(circle)
if circle_len==n:
    circle_idx=k%(circle_len)
    ans=circle[circle_idx][1]

elif k<circle_in:
    ans=tele.index(k)
else:
    k=k-(circle_in-1)
    circle_idx=k%(circle_len)
    ans=circle[circle_idx][1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x, cnt):
  if visited[x-1] != -1:
    return [x, visited[x-1], cnt-visited[x-1]]
  else:
    visited[x-1] = cnt
    return tami(a[x-1], cnt+1)

def nasu1(x, cnt):
  if cnt == start:
    return x
  else:
    return nasu1(a[x-1], cnt+1)

def nasu2(x, cnt):
  if cnt == num:
    return x
  else:
    return nasu2(a[x-1], cnt+1)

N,K = IL()
a = IL()

visited = [-1]*N
i, start, roop = tami(1, 0)
if K <= start:
  print(nasu1(1, 0))
else:
  #print(visited)
  num = (K-start)%roop
  #print(start,roop,num)

  print(nasu2(i, 0))

Submission status: Wrong Answer

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

tmp = 1
num = []

for i in range(N):
    num.append(tmp)
    tmp = A[tmp-1]
    if tmp == 1:
        break

print(num[K%len(num)])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a=list(map(int,input().split()))
cnt=[0]*(n+1)
x=1
cnt[x]=a[0]
rep=1
ans=[1]
for i in range(2*n):
    x=a[x-1]
    
    if cnt[x]!=0:
        ans.append(x)
        break 
    else:
        rep+=1
        cnt[x]=a[x-1]
        ans.append(x)
aa=[]
val=ans[-1]

for i in range(len(ans)):
    if ans[i]==val:
        break
for j in range(i,len(ans)-1):
    aa.append(ans[j])
print(aa[(k-i)%len(aa)])

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
P = 1
L =[]
while not(P in L):
    L.append(P)
    P= A[P-1]
C = L.index(P)
L = L[C:]
B=(K-C)%len(L)    
print(L[B])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [1]+a
v = [-1 for _ in range(n+1)]
v[1] = 0
x = a[1]
c = 1

while k > 0 and v[x] < 0:
    y = a[x]
    v[y] = v[x]+1
    x = y
    k -= 1
    c += 1

if k==0:
    print(x)
else:
    z = c - v[x]
    if z != 0:
        k = k%z
    else:
        k = k%c
    while k > 0:
        k -= 1
        x = a[x]
    print(x)

Submission status: Wrong Answer

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

arr = [1]
cnt = 1

for i in range(N):
  if i == 0:
    s = List[i]
    arr.append(s)
    cnt += 1
  else:
    if List[s-1] in arr:
      b = arr.index(List[s-1])
      break
    else:
      s = List[s-1]
      arr.append(s)
      cnt += 1
      
l = len(arr)
c = (K-b) % (l-b)

if K-b > 0:
  print(arr[b+c])
else:
  print(arr[K-1])

Submission status: Wrong Answer

Solution code:
n,k = map(int ,input().split())
A = tuple(map(int, input().split()))
seen = [-1]*n
tmp = 0
count = 0

while True:
    tmp = A[tmp]-1
    count +=1
    if seen[A[tmp]-1] != -1:
        seennum = seen.count(1)



        tm = A[tmp]-1
        se = [-1]*n
        roopmem = []
        while True:
            roopmem.append(tm)
            tm = A[tm]-1
            if se[A[tm]-1] != -1:
                roop = se.count(1)
                break
            se[A[tm]-1] = 1
        break

    seen[A[tmp]-1] = 1

if k<n:
    no = 0
    for i in range(k):
        no = A[no]
    print(no)
else:
    tmp = k-seennum+roop
    tmp %= roop
    print(roopmem[tmp+1]+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

n,k=map(int, input().split())
a=list(map(int, input().split()))
isUsed=[False]*n

path = [1]
#isUsed[0] = True

i = 1
while(True):
    idx = i-1
    if isUsed[idx]: #既に行ったことがある町であれば
        #print("行ったことのある町です")
        #print("i", i)
        start = path.index(i)
        break
    else:
        isUsed[idx] = True
        path.append(a[idx])
        #print(path)
        i = a[idx]


if k >= start:
    #print(start)
    #print(len(path)-1)
    num = len(path) - 1 - start
    lis_mod = path[start:start+num]

    mod = len(lis_mod)

    #print("k-start",k-start)
    tmp = (k-start)%mod
    #print("k-start % mod", tmp)
    print(lis_mod[tmp])
else:
    print(path[k-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().strip().split())
L = list(map(int, input().strip().split()))
L=[v-1 for v in L]

if L[0]==0:
    print(0)
    exit()

seen=set()
cur=0
cnt=0

while cur not in seen:
    seen.add(cur)
    cnt+=1
    # last=cur
    cur=L[cur]
intersec=cur
cur=0
cnt2=0
while cur!=intersec:
    cur=L[cur]
    cnt2+=1
loopSize=cnt-cnt2
ans=0
for _ in range((k-cnt2)%(loopSize)+cnt2):
    ans=L[ans]
print(ans+1)

Submission status: Wrong Answer

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

now_in=0
count=0
if k>n:  
    for i in range(n):
        now_in=a[now_in]-1
        count+=1
        if now_in==0:
            break
    k = k%count

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

now_in +=1
print(now_in)

Submission status: Wrong Answer

Solution code:
import collections
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [i-1 for i in A]
N = collections.Counter()
t = 0
cnt = 0
for i in range(n):
    if N[t]:
        break
    N[t] = 1
    t = A[t]
    cnt += 1
k -= cnt
T = []
for i in N:
    T.append(i)
tmp = T.index(t)
S = T[tmp:]
s_len = len(S)
ind = k % s_len
print(S[ind] + 1)

Submission status: Wrong Answer

Solution code:
N,K = (int(x) for x in input().split())
A = list(map(int, input().split()))
route = []
temp = 0
for i in range(N):
    route.append(temp)
    temp = A[temp]-1
    if temp == 0:
        break
if K >= len(route):
    print(route[K%len(route)]+1)
else:
    print(route[K-1]+1)

Submission status: Wrong Answer

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

l = []
kari = 0


for i in range(N*2):
    l.append(A[kari-1])
    kari = A[kari-1]
    
    zyuuhuku = set(l)
    if len(zyuuhuku) != len(l):
        tometatokoro = A[kari-1]
        break
    


    
    

#繰り返しでもどったところの列番号
aaaa = l.index(tometatokoro)

#繰り返すループの長さ
kurikaesi = len(l)-aaaa

#ループ繰り返す余り
ans = K % kurikaesi


ans = ans + aaaa

print(l[ans])

Submission status: Wrong Answer

Solution code:
n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
idx=0
li=[]
for i in range(k):
    idx=a[idx]-1
    if idx==1:
        break
    li.append(a[idx])

size=len(li)
print(li[k%size])

Submission status: Wrong Answer

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 and cnt <= k:
        visited.append(temp)
        visitedSet.add(temp)
        temp = nums[temp]
        cnt += 1
    if temp not in visitedSet:
        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: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
check=[0]*(N)
check[0]=1
D=[]
C=[0]
p=0
for i in range(N):
  pp=A[p]-1
  if check[pp]==0:
    check[pp]=1
    C.append(pp)
    p=pp
  else:
    roop=pp
    break
    
rs=C.index(roop)
if K<=rs-1:
  print(A[K]+1)
else:
  K-=(rs-1)
  C=C[rs:]
  e=K%(len(C))
  print(C[e-1]+1)

Submission status: Wrong Answer

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:
        print(temp_list[(k - i) % (i - temp_dict[temp]) + temp_dict[temp]])
        break
    temp_dict[temp] = i
    temp_list.append(temp)
    ci = temp

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[0]
a.extend(list(map(int,input().split())))
loop=[]
now=0
if n<k:
    for  i in range(1,n+1):
        if i==1:
            now=a[1]
            loop.append(now)
        else:
            now=a[now]
            if now!=a[1]:
                loop.append(now)
            else:
                break
    len=len(loop)
    count=k%len
    if count ==0:
        print(loop[-1])
    else:
        print(loop[count-1])
else:
    for i in range(1,k+1):
        if i==1:
            now=a[1]
        else:
            now=a[now]
    print(now)

Submission status: Wrong Answer

Solution code:
n,k= map(int, input().split())
a= list(map(int, input().split()))
a=[0]+a
x=[0]*(n+1)
s=a[1]
x[1]=1
v1=[1]
cnt1=1
v2=[]
cnt2=0
for i in range(10**7):
    print(s,a[s])
    if x[s]==0:
        x[s]+=1
        cnt1+=1
        v1.append(s)
        s=a[s]

    elif x[s]==1:
        cnt2+=1
        x[s] += 1
        v2.append(s)
        s = a[s]
    else:
        break

if k<cnt1:
    print(v1[k])
else:
    q=(k-cnt1)%cnt2
    print(v2[q])

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

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

def readInts():
  return list(map(int,input().split()))
def main():
    n,k = readInts()
    A = readInts()
    root = []
    ok = True
    l = 0
    while True:
        if ok:
            a = 1
            ok = False
        else:
            a = root[-1]
        if not A[a-1] in root:
            root.append(A[a-1])
        else:
            j = 0
            for i in range(len(root)):
                if A[a-1] == root[i]:
                    j = i
                    break
            root = root[j:]
            l = j
            #print(root)
            break

    #print(root)
    k = k - (l+1) if k - (l+1) >= 0 else k
    print(root[k%len(root)])
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

(town, tele)=[int(x) for x in input().split()]
pos=[int(x) for x in input().split()]
move=[pos[0]]
while True:
  move.append(pos[move[-1]-1])
  if Counter(move)[move[-1]] > 1:
    break
loop_move=move[move.index(move[-1]):-1]
print(loop_move[(tele-(len(move)-1))%len(loop_move)-1])

Submission status: Wrong Answer

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

route = [1]
next = A[0]

while(True):
    if next not in route:
        route.append(next)
        next = A[next-1]
    elif A[0] == next:
        break
    else:
        route = route[route.index(next):]
        break
print( A[K % len(route)])

Submission status: Wrong Answer

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

went={i:0 for i in range(1,n+1)}

now=1
cnt=1
for i in range(n+1):
    if went[now]>0:
        t=cnt-1
        s=went[now]
        break
    else:
        went[now]=cnt
        now=A[now-1]
        cnt+=1


if k <= t:
    val=k+1
else:
    val=((k+1-t)%(t-s+1)-1)%(t-s+1)+s
for ele in went:
    if went[ele]==val:
        print(ele)
        break

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


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

    pos = A[1]
    visited = {1}
    while pos not in visited:
        visited.add(pos)
        pos = A[pos]
    
    start = pos
    loop = 1
    pos = A[pos]
    while pos != start:
        pos = A[pos]
        loop += 1
    
    dist = 0
    pos = 1
    while pos != start:
        pos = A[pos]
        dist += 1

    print("dist={}, loop={}".format(dist, loop))
    
    if dist < K:
        K -= dist
        K %= loop
        pos = start
        for _ in range(K): pos = A[pos]
        print(pos)
    else:
        pos = 1
        for _ in range(K): pos = A[pos]
        print(pos)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

roop = N
first = 0
now = 1
already = [1]
for i in range(N):
  go_town = A_list[now-1]
  if go_town in already:
    already.append(go_town)
    indexs = [i for i, x in enumerate(already) if x == go_town]
    first = already.index(go_town)
    roop = already[first:-1]
    break
  already.append(go_town)
  now = go_town

real_K = (K - first) % len(roop)
print(roop[real_K])

Submission status: Wrong Answer

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, K = list(map(int, input().split()))
    A = [x-1 for x  in list(map(int, input().split()))]

    len_cycle = 0
    start = 0
    while True:
        start = A[start]
        len_cycle += 1
        if start == 0 or len_cycle > N:
            break
    len_move = K % len_cycle
    start = 0
    for _ in range(len_move):
        start = A[start]
    print(start+1)
    pass

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = [0] + list(map(int, input().split()))
r = [1]
k += 1
now = 1
for i in range(n):
   now = a[now]
   if now in r: 
     break
   r.append(now)
I = r.index(now)
if I != 0: 
  k -= I
  r = r[I:]
print(r[-1] if k%len(r)==0 else r[k%len(r)-1])

Submission status: Wrong Answer

Solution code:
def solve(N, K, A):
    slow, fast = 1, 1
    is_first = True
    while is_first or slow != fast:
        is_first = False
        slow = A[slow - 1]
        fast = A[A[fast - 1] - 1]
    fast = 1
    steps_before_entering_cycle = []
    while slow != fast:
        steps_before_entering_cycle.append(slow)
        slow = A[slow - 1]
        fast = A[fast - 1]

    if K < len(steps_before_entering_cycle):
        return steps_before_entering_cycle[K]

    cycles = [slow]
    while A[slow - 1] != cycles[0]:
        cycles.append(A[slow - 1])
        slow = A[slow - 1]
    return cycles[(K - len(steps_before_entering_cycle)) % len(cycles)]

if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    print(solve(N, K, A))

Submission status: Wrong Answer

Solution code:
n, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]

t = 0
l = []
c = 0
d = {}
while True:
    d[t+1] = c
    c += 1
    l.append(t+1)
    t = a[t] - 1
    # if t == 0:
    #     break
    if t + 1 in d:
        s = l[d[t+1]:]
        q = t + 1
        break
# print(l)
# print(s)
# print(d)
# print(q)
if q == 1:
    print(s[k % len(s)])
else:
    if k <= q:
        print(l[k])
    else:
        print(s[(k-q) % len(s)])

Submission status: Wrong Answer

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

used = set()
history = []

cur = 0
used.add(0)

while True:
    history.append(cur)
    next_cur = A[cur] - 1
    if next_cur in used:
        loop_start = history.index(next_cur)
        break
    used.add(next_cur)
    cur = next_cur

# print(history)
# print(loop_start)
B = history[loop_start:]
result = B[(K-loop_start) % len(B)]

print(result+1)

Submission status: Wrong Answer

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

N, K = map(int,input().split())
A = list(map(int, input().split())) 
check = [0]*N
tele_lis = []
global start
start = []
def tele(x):
    check[x-1] = 1
    tele_lis.append(x)
    if check[A[x-1]-1] == 0:
        tele(A[x-1])
    else:
        start.append(A[x-1])
        return
tele(1)
for i in range(N):
    if start[0] == tele_lis[i]:
        break
    
print(tele_lis[i::][(K-i) % (sum(check)-i)])

Submission status: Wrong Answer

Solution code:
def resolve():
    n, g = map(int, input().split())
    a = list(map(int, input().split()))
    ar = [-1] * n
    k = 0
    now = 0
    for i in range(n+1):
        if ar[now] == -1:
            ar[now] = k
            now = a[now]-1
            k += 1
        else:
            start = ar[now]
            startnode = now
            end = k
    if g <= start:
        ans = 0
        for i in range(n):
            if ar[i] == k:
                ans = i+1
    else:
        g -= start
        g %= (end-start)
        now = startnode
        for i in range(g):
            now = a[now]-1
        ans = now + 1
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

N, K = map(int, input().split())
A = list(map(int, input().split()))
T = set([0])  # 0-indexed

c = 0  # 0-indexed
for i in range(N + 1):
    c = A[c] - 1
    # print('c', c)
    if c not in T:
        T.add(c)
    else:
        break
C = deque([c])
T = set([c])  # 0-indexed
for i in range(N + 1):
    c = A[c] - 1
    # print('c', c)
    if c not in T:
        T.add(c)
        C.append(c)
    else:
        break
c2 = 0  # 0-indexed
S = deque([0])
for i in range(N + 1):
    c2 = A[c2] - 1
    if c2 == c:
        break
    else:
        S.append(c2)
# print('C', C)
# print('S', S)
# print('len(C), len(S)', len(C), len(S))

if C[0] == 0:
    mod = K % len(C)
    ans = C[mod]
else:
    if len(S) >= K:
        ans = S[K - 1]
    else:
        mod = (K - len(S)) % len(C)
        ans = C[mod]
print(ans + 1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = [1]+a
v = [-1 for _ in range(n+1)]
v[1] = 0
x = a[1]
c = 1

while k > 0 and v[x] < 0:
    y = a[x]
    v[y] = v[x]+1
    x = y
    k -= 1
    c += 1

if k==0:
    print(x)
else:
    z = c - v[x] -1
    if c==0:
        import sys
        print(x)
        sys.exit()
    elif z != 0:
        k = k%z
    else:
        k = k%c
    while k > 0:
        k -= 1
        x = a[x]
    print(x)

Submission status: Wrong Answer

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

# from fractions import gcd
from math 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()]

root = [1]
index = 0

for i in range(N):
    if A[index] in root:
        ho = root.index(A[index])
        hoge = root[ho:]
        break

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

nokori = (K-ho) % len(hoge)

print(hoge[nokori])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A = [a - 1 for a in A]
visited = [0] * n

i = 0
lp = 0
step = []
while visited[i] == 0:
  visited[i] = 1
  next_visit = A[i] 
  step.append(i)
  lp += 1
  i = next_visit

lp_start = step.index(i)
syuki = lp - lp_start

if lp_start > k:
  ans = step[k]
else:
  cnt = (k - lp_start) % syuki
  ans = step[lp_start:][cnt] + 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

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

visited = set()
visited.add(0)
trace = []
cur = 0
while True:
    trace.append(cur)
    if A[cur] in visited:
        cur = A[cur]
        break
    visited.add(A[cur])
    cur = A[cur]

pre = 0
for i, a in enumerate(trace):
    if a == cur:
        pre = i

loop = len(trace) - pre

if K <= pre:
    ans = trace[K - 1]
else:
    if loop == 0:
        ans = trace[pre::][0]
    else:
        r = (K - pre) % loop
        ans = trace[pre::][r]

print(ans + 1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a=list(map(int,input().split()))
cnt=[0]*(n+1)
x=1
cnt[x]=a[0]
rep=1
ans=[1]
for i in range(n):
    x=a[x-1]
    
    if cnt[x]!=0:
        ans.append(x)
        break 
    else:
        rep+=1
        cnt[x]=a[x-1]
        ans.append(x)
aa=[]
val=ans[-1]

for i in range(len(ans)):
    if ans[i]==val:
        break
for j in range(i,len(ans)-1):
    aa.append(ans[j])
print(aa[(k-i)%len(aa)])

Submission status: Wrong Answer

Solution code:
#author: raghav_0901
from math import *

mod = (10**9) + 7


def _in():
    return [int(x) - 1 for x in input().split(' ')]


def main():
    n, k = [int(x) for x in input().split(' ')]
    arr, dp = _in(), [0, ]
    vis = [False] * (n)
    vis[0], nxt = True, arr[0]
    while(not vis[nxt] and len(dp) < k):
        dp.append(nxt)
        vis[nxt] = True
        nxt = arr[nxt]
    if(len(dp) == k):
        print(dp[-1] + 1)
    else:
        i = 0
        while(dp[i] != nxt):
            k, i = k - 1, i + 1
        rem = k % (len(dp) - i)
        print(dp[rem + i] + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(pow(10, 6))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, k = sp()
arr = l()
answer = [1]
s = {1}
index = 1
while True:
    temp = arr[answer[-1]-1]
    if temp in s:
        index = temp
        break
    s.add(temp)
    answer.append(temp)
if k <= len(answer)-1:
    out(answer[k-1])
    exit()
k -= (len(answer)-1)
temp = answer.index(index)
answer = answer[temp:]
k %= len(answer)
if k == 0:
    k = len(answer)
out(answer[k-1])

Submission status: Wrong Answer

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
	while(zz <= k):
		last = curr + 1
		curr = l[curr]-1
		zz += 1
		if(done[curr+1] != 0):
			last = curr+1
			break
		else:
			done[curr+1] = zz
	if(len(done) == 1):
		return l[0]
	zz -= 1
	mod = k%zz
	k = k - done[last] + 1
	cycle = zz - done[last] + 1
	mod = k%cycle
	find = mod+done[last]
	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: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, k = ns()
    a = na()
    a = [ai - 1 for ai in a]

    junkan_point = 0
    visited = [0, a[0]]
    next = a[0]
    for _ in range(n):
        if a[next] in visited:
            flg = True
            junkan_point = a[next]
            break
        else:
            visited.append(a[next])
            next = a[next]

    junkan_visited = visited[visited.index(junkan_point):]

    tmp = len(visited) - len(junkan_visited)
    if k < tmp:
        print(k)
    else:
        idx = (k-tmp) % len(junkan_visited)
        print(junkan_visited[idx] + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
C = {i:0 for i in range(1,N+1)}
loop = [1]
C[1] = 1
tmp = A[0]
for i in range(N):
    x = A[tmp-1]
    #print(x)
    if C[x] == 1:
        loop.append(tmp)
        X = x
        break
    else:
        loop.append(tmp)
        C[x] = 1
        tmp = x
#print(loop)
lenloop = len(loop)
tail = 0
for i in loop:
    if i != X:
        tail += 1
    else:
        break
loop = loop[tail:]
K -= tail
lenloop -= tail
XX = K % lenloop
ans = loop[XX]
#print(tail,loop,XX)
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[i-1 for i in A]
c=A[A[0]]
if c==0:
  print(c+1)
  exit()

s=set()
s.add(A[0])
d=[]
d.append(A[0])

while True:
  if c in s:
    break
  s.add(c)
  d.append(c)
  c=A[c]

a=d.index(c)
K-=a

mod=len(s)-a
K%=mod

ans=A[0]
for i in range(a):
  ans=A[ans]

for i in range(K-1):
  ans=A[ans]
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys

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

#各頂点が白(0)か黒(1)か
flag = [-1 for _ in range(n)]

#dfsで色を塗っていく
#頂点の数をN、辺の数をMとすると、O(N+M)で解ける
stack = [a[0]-1]
flag[0] = 0
count = 0
while stack:
	u = stack.pop()
	if flag[u] == -1:
		stack.append(a[u] - 1)
		count += 1
		if count == k:
			print(a[u])
			sys.exit()
		flag[u] = count
	else:
		loop = count - flag[u] + 1
		#print(count,flag[u],loop)
		num = (k - flag[u]) % loop
		#print(num)
		break

if num == 0:
	print(u + 1)
else:
	ans = a[u]
	for i in range(num-1):
		ans = a[ans-1]
	print(ans)

Submission status: Wrong Answer

Solution code:
n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
a.insert(0,-1)

freq=[]
for i in range(n+1):
	freq.append(0)

pos=1
pos=a[pos]
cycle=[]
while freq[pos]==0:
	freq[pos]+=1
	cycle.append(pos)
	pos=a[pos]

flag=0
c1=[]
c2=[]
for i in range(len(cycle)):
	if cycle[i]==pos:
		flag=1
	if flag==0:
		c1.append(cycle[i])
	else:
		c2.append(cycle[i])

#print(c1,c2)

l1=len(c1)
l2=len(c2)

if k<=l1:
	print(c1[l1-1])
else:
	k-=l1
	print(c2[(k-1)%l2])

Submission status: Wrong Answer

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

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

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

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

k -= cnt
k %= mod

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

print(a[next - 1])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
chk = [0] * N
start = -1
ido = [0]
chk[0] = 1
index = 0
cnt = 0
while True:
    index = a[index] - 1
    if chk[index] == 0:
        chk[index] += 1
        cnt += 1
        ido.append(index)
    else:
        start = index
        break

if cnt > K:
    print(a[ido[K]])
    exit()
tmp = ido.index(start)
ido = ido[tmp:]
K -= tmp
print(ido[K % len(ido)] + 1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i)-1 for i in input().split()]
loc = 0
lst = [False]*n
lst[0] = True
while True:
    if lst[a[loc]]:
        x = a[loc]
        break
    loc = a[loc]
    lst[loc] = True
cnt = 0
loc = 0
if x != 0:
    while True:
        loc = a[loc]
        cnt += 1
        if loc == x: break
cnt2 = 0
while True:
    loc = a[loc]
    cnt2 += 1
    if loc == x: break
k -= cnt
k %= cnt2
loc = x
while k > 0:
    loc = a[loc]
    k -= 1
print(loc+1)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
l = [0]
w = 0
while True:
    w = a[w] - 1
    cnt += 1
    if w in l:
        idx = l.index(w)
        freq = cnt - idx
        n = (k - idx)
        n %= freq
        for i in range(n):
            w = a[w] - 1
        print(w+1)
        exit()
    else:
        l.append(w)