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:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,K = inputMap()
	A = inputList()

	if N == 1:
		print(1)
		sys.exit()

	mati = [0 for i in range(N)]
	for i,val in enumerate(A):
		mati[i] = val-1

	aaaaa = 0
	if K <= 100000:
		for i in range(K):
			#print(aaaaa)
			aaaaa = mati[aaaaa]

		print(aaaaa+1)
		sys.exit()


	tugi = 0
	gizi = {}
	gizi2 = {}
	saigo = inf
	ans = []
	cnts = 0
	flg = False
	for i in range(K):
		tugi = mati[tugi]
		if flg == False:
			cnts += 1
			if tugi in gizi:
				flg = True
				ans.append(saigo)
				ans.append(tugi)
				gizi2[saigo] = 1
				gizi2[tugi] = 1
			else:
				gizi[tugi] = 1
				saigo = tugi
		else:
			if tugi in gizi2:
				break
			else:
				ans.append(tugi)
				gizi2[tugi] = 1

	if len(ans) == 0:
		print(tugi)
		sys.exit()

	tmp = len(ans)
	cnts = cnts - len(ans)
	kotae = (K-cnts+1) % (tmp)

	#print(cnts)
	#print(kotae)
	#print(ans)
	print(ans[kotae]+1)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
town=list(map(int,input().split()))
cnt=1
a=1
li=[1]
while len(li)==cnt:
  a=a-1
  a=town[a]
  li.append(a)
  cnt+=1
  li=list(set(li))
  if len(li)!=cnt:
    start=a
if cnt==0:
  x=k+1
else :
  s=1
  coun=1
  while s!=start:
    s=town[s-1]
    coun+=1
  x=(k+2-coun)%(cnt-coun)
  x=x+coun-1
  
ans=1
if x!=0:
  for i in range(x-1):
    ans=town[ans-1]
else:
  for i in range(cnt-coun-1):
    ans = town[ans-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array([int(x) for x in input().split()])
B = np.zeros(N)
C = np.zeros(N)
pos = 0
# B[0] = 1
for i in range(N*2):
    B[pos] += 1
    if C[pos] == 0:
        C[pos] = i+1
    pos = A[pos] - 1
ans = K - len(B[B <= 1]) + len(B[B == 0])
ans %= len(B[B > 1])
D = sorted(C[B > 1])
tmp = D[ans]
index = np.where(C == tmp)
print(*index[0] + 1)

Submission status: Wrong Answer

Solution code:

def q4():
    N, K = [int(i) for i in input().split(" ")]
    A = [-1] + [int(i) for i in input().split(" ")]

    if K < N:
        current = 1
        for i in range(K):
            current = A[current]
        return

    # ループをみつけてKの数を減らす。
    # ループをみつける→同じ場所に2回きたらループとみなす
    # ループがないことはありえる？　ない

    # ループを見つける
    arrived = []
    current = 1
    loop_start_station = -1
    while True:
        arrived.append(current)
        current = A[current]
        if current in arrived:
            loop_start_station = arrived.index(current)
            arrived = arrived[loop_start_station:]
            break

    K = K - loop_start_station
    K = K % len(arrived)
    print(arrived[K])
        
q4()

Submission status: Wrong Answer

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

V = [0 for i in range(n)]
P = [-1 for i in range(n)]
cp = 1
t = 0
while 1:
    #print('V = ', V)
    V[cp - 1] += 1
    if V[cp - 1] < 2:
        P[cp - 1] = t
    else:
        break
    cp = A[cp - 1]
    t += 1

pret = P[cp - 1]
t = t - pret
#print('pret = ', pret)
#print('t = ', t)
#print('P = ', P)

if k <= pret:
    pass
else:
    k = k - pret
    P = list(map(lambda x: x - pret, P))
#print('P = ', P)

ans = 0
l = k % t
for i in range(n):
    if P[i] == l:
        ans = i + 1
        break
    else:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

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


i=b.index(i)
a=b[:i]
c=b[i:]
#print(a,c)
if(k<=len(a)):
    print(a[k-1])
else:
    k-=len(a)
    k%=len(c)
    print(c[k])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    lenA = len(A)

    tmp = []
    path = []
    i = 1
    for _ in range(1, lenA + 1):
        if i in path:
            itmp = path.index(i)
            break
        path.append(i)
        i = A[i-1]

    lenpath = len(path)
    if K >= lenpath:
        jtmp = (K-itmp)%(lenpath-itmp)
        ans = path[itmp+jtmp]
    else:
        ans = path[K-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lis = list(map(int, input().split()))
res = [1]
rott = []
for i in range(n):
    a = lis[res[-1]-1]
    if a in res:
        rott.append((res.index(a), i+1))
    res.append(a)
x, y = rott[0]
mm = (m - x) % (y - x)
print(res[x + mm])

Submission status: Wrong Answer

Solution code:
# D

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

def compute(city, K):
    for i in range(K):
        # print('\t', city)
        city = As[city-1]
    print(city)

cities_visited = [False] * N
i = 0
city = 1
city_visited_time = {}

while not cities_visited[city - 1]:
    # print(city)
    cities_visited[city - 1] = True
    city_visited_time[city-1] = i
    city = As[city-1]
    i += 1

loop_start = city_visited_time[city-1]
loop_end = i

div = (K - loop_start) // (loop_end - loop_start + 1)
# print(loop_start, loop_end, div, K % (loop_end - loop_start + 1))
compute(city, K % (loop_end - loop_start + 1) + loop_start + 1)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
x = A[0]
c = [-1]*N
c[0] = 1
i = 1
while True:
    i += 1
    c[x-1] = i
    x = A[x-1]
    if c[x-1] != -1:
        t = i-c[x-1]+1
        s = c[x-1]
        break
x = A[0]
if K<=N:
    for i in range(K-1):
       x = A[x-1]
else:
    temp = (K-(s-1))%t+s-1
    for i in range(temp-1):
        x = A[x-1]
print(x)

Submission status: Wrong Answer

Solution code:
def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y

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

A = intlist(input().split())

now = 1
past = [1]

for j in range(0,len(A)):
    now = A[now-1]
    if now in past:
        past.append(now)
        break
    past.append(now)





for k in range(len(past)):
    if past[k] == past[len(past)-1]:
        count = k
        break
        
for l in range(count):
    del past[0]

del(past[len(past)-1])


B = (K - count) % len(past)
print(past[B])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, K = map(int, readline().split())
A = list(map(lambda x: x - 1, map(int, readline().split())))
visited = [False for i in range(N)]

cur = 0
cycle = []
start = 0
while True:
    if visited[cur]:
        start = cur + 1
        break

    visited[cur] = True
    cycle.append(cur + 1)
    cur = A[cur]

cycle_start_idx = 0
for i in range(len(cycle)):
    if cycle[i] == start:
        cycle_start_idx = i
        break

if K <= cycle_start_idx:
    print(cycle[cycle_start_idx])
    exit()


cycle_len = len(cycle) - cycle_start_idx
idx = (K - cycle_start_idx) % cycle_len
print(cycle[idx + cycle_start_idx])

Submission status: Wrong Answer

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

rs = 0
p = -1
r = ""
d = 1
# i回目
for i in range(K):
  r += str(d)
  d = A[d - 1]
  for j in range(len(r)):
    if r[j] == str(d):
      rs = j
      p = i - j + 1
      break
  if p != -1:
    break
if p == -1:
  print(r[-1])
else:
  print(r[rs+(K-rs)%p])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dict={}
for i in range(n):
    dict[i]=a[i]-1 #i番目の町からどこにつくか
tmp=0#現在知
num2city={}
city2num={}
city2num[0]=0#どのまちが何回目か
num2city[0]=0#j回目にどこにいるか
for j in range(k):
    tmp=dict[tmp]#現在地更新
    if tmp not in num2city.values():#現在地がまだきたことない
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j-1
        if term==0:
            break
        r=res%term
        #print(mae,term,res,r)
        temp=num2city[mae+r]
        break
  #  print(tmp+1)
    

print(tmp+1)

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
lis = list(map(int,input().split()))
m = b%a
k = lis[m-1]
print(lis[k-1])

Submission status: Wrong Answer

Solution code:
N,K = [int(i) for i in input().split()]
A = [int(i)-1 for i in input().split()]

place = [0]
now = 0
while True:
    now = A[now]
    place.append(now)
    place_set = set(place)
    if len(place) != len(place_set):
        break

t = place.index(place[len(place)-1])
print(place)
print(t)
if K <= t:
    print(place[K-1]+1)
    exit()
K -= t
print(K)
K %= (len(place)-t-1)
print(K)
print(place[K+t]+1)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A_li = list(map(int,input().split()))
junban = [1,]
idx = 0
flag = False
flag2 = False
check = [0]*N
while True:
    tmp = A_li[idx]
    if check[idx]:
        if flag:
            flag = True
        else:
            flag2 = True
    junban.append(tmp)
    check[idx] = 1
    idx = tmp - 1
    if flag2:
        break
#print(junban)
syuuki = []
check = [0]*N
for i in junban[::-1]:
    syuuki.append(i)
    if check[i-1]:
        break
    check[i-1] = 1
syuuki = syuuki[::-1][:-1]
#print(syuuki)
saisyo = 0
a = len(syuuki)
for i in range(len(junban)):
    if junban[i:i+a] == syuuki:
        saisyo = i
        break
#print(saisyo)
indekkusu = (K-saisyo)%len(syuuki)
print(syuuki[indekkusu])

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
if k >= cnt:
    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()))

now = 1
r = [now]
while not A[now - 1] in r:
    r.append(A[now-1])
    now = A[now-1]
x = r.index(A[now-1])
r_x = r[x:]
print(r_x[(K-x)%len(r[x:])])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    A=[1]+A
    route=[1]
    st=set()
    st.add(1)
    now=1
    while True:
        now=A[now]
        if now in st:
            break
        route.append(now)
        st.add(now)
    
    idx=route.index(now)
    if K-idx+1>0:
        if len(route)-1!=idx:
            print(route[idx-1+(K-idx+1)%(len(route)-idx)])
        else:
            print(route[-1])
    else:
        print(route[K])
    

main()

Submission status: Wrong Answer

Solution code:


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
cur = 0
list = []
for i in range(N+1):
  cur = A[cur-1]
  if (cur in list):
    loop = len(list)
#    print("loop", loop)
  list.append(cur)
#  print(cur)

cur = 0

for i in range((K % loop) + 2):
  cur = A[cur-1]

print(cur)

Submission status: Wrong Answer

Solution code:
#D - Teleporter
N,K = map(int, input().split())
A = list(map(int, input().split()))
DP = []
DP.append(A[0])
for i in range(N):
    DP.append(A[DP[i]-1])

print(DP[K%len(DP)-1])

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
mod = -1
num = [0]
prev = 0
cnt = 0
# num.append(0)
while True:
    # print(num, cnt)
    if not a[prev] in num:
        num.append(a[prev])
        prev = a[prev]
    else:
        lpst = a[prev] 
        mod = cnt - num.index(a[prev]) + 1
        k -= num.index(a[prev])
        k %= mod
        break
    cnt += 1

# print(mod, lpst, k)
now = lpst
while k:
    now = a[now]
    k -= 1
        
# while k > 0:
#     if now == lpst:
#         k %= mod
#     if k == 0:
#         break
#     now = a[now]
#     k -= 1
#     print(now, k)


print(now+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
a=[0]+p
flag=0
bef=1
town=[1]
town_set=set(town)
while flag==0:
    if not a[bef] in town_set:
        town.append(a[bef])
        town_set.add(a[bef])
        bef=a[bef]
    else:
        flag=1
        memo=a[bef]
for j in range(len(town)):
    if town[j]==memo:
        num=j
x=len(town)-num
y=(k-num)%x
print(town[num+y])

Submission status: Wrong Answer

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

b = 1
while b >= 0:
    if b in A:
        
        break
    elif b not in A:
        A.append(b)
        
        b = a[b-1]

c =A.index(b)
d = len(A) -c    

e = (K - (len(A)-d)) % d

print(A[c+e])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
n, k, *a = map(int, open(0).read().split())
F = [0 for _ in range(n)]  # 来た？
T = [None for _ in range(n)]  # いつ来た？
def main(now, time, K):
    time += 1
    if F[now-1]:
        P = T[now-1]
        print(T.index(P + (K - time + 1) % (time - P)) + 1)
        exit()
    F[now-1] = 1
    T[now-1] = time
    main(a[now-1], time, K)

main(1, 0, k)

Submission status: Wrong Answer

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


a = list(map(int,input().split()))
b = [0 for i in range(2*10**5)]
l = []
x = 1

if k <= 2*10**5:
    for i in range(k-1):
        x = a[x-1]
    

    print(x)
    exit()



for i in range(2*10**5):
    if b[x] == 0:
        b[x] += 1
    else:
        res = x+1
        break
    
    l.append(x+1)
    x = a[x]-1




roup = l[l.index(res):]

k -= (len(l)-len(roup))

print(roup[k % len(roup)])

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

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

tel = [-1] * N
flag = True
i = 0
time = 1
while True:
    # print(i, end=" ")
    if time == K:
        print(A[i]+1)
        flag = False
        break
    
    if tel[i] == -1:
        tel[i] = [time, A[i]-1]
        i = A[i]-1
    else:
        # i = A[i]-1
        break
        # pass
    
    time += 1
    # print(time, tel)
# print()
# print(time-1)
# print(time - tel[i][0])
# print((K - (time-1)) % (time - tel[i][0]))

if flag:
    for _ in range((K - (time-1)) % (time - tel[i][0])):
        i = A[i]-1

    print(i+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))

dst = defaultdict(int)

for i, a in enumerate(A, 1):
    dst[i] = a

done = [0 for _ in range(N + 1)]
done[1] = 1
hist = [1]

now = 1
cnt = 0
while True:
    now = dst[now]
    cnt += 1
    if done[now] == 0:
        done[now] = 1
        hist.append(now)
    else:
        syuki = cnt - hist.index(now)
        print(hist[hist.index(now) + (K - cnt) % syuki])
        exit()

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
a = list(map(int, input().split()))
c = 1
s = 0
b = [0]*(n+1)
b[1] = 1
d = [0]*(n+1)
d[1] = 0

for i in range(2*n):
    c = a[c-1]
    b[c] += 1
    if b[c] == 2:
        s = i+1 - d[c]
        f = d[c]
        break
    d[c] = i+1

e = c
S = (k-f)%s
for i in range(S):
    e = a[e-1]
    #print(e)
#print(s)
#print(c)
#print(f)
print(e)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
c=[0]*n
d=[0]*n
g=0
count=1
c[0]=1	
while 2 not in c:
  g=l[g]-1
  if c[g]==1:
    a=d[g]
    c[g]+=1
    cp=g
  else:
    c[g]+=1
    d[g]=count
    count+=1
    
if k-count<=0:
  now=0
  for j in range(k+1):
    now=l[now]-1
  print(now+1)
  
else:
  r=(k-a)%(count-a)
  now=l[cp]
  for j in range (r+1):
    now=l[now]-1
  print(now+1)

Submission status: Wrong Answer

Solution code:
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
graph=[0 for i in range(N+1)]

for i,value in enumerate(A):
    graph[i+1]=value

stack=[1]
visited=[0 for i in range(N+1)]
C=[]
ct=0
while stack:
    x=stack.pop()
    if visited[x]==0:
        ct+=1
        visited[x]+=1
        stack.append(graph[x])
        C.append(x)
        
stack=[graph[C[-1]]]
visited=[0 for i in range(N+1)]
counter=0
while stack:
    x=stack.pop()
    if visited[x]==0:
        visited[x]+=1
        stack.append(graph[x])
        counter+=1
        
stack=[graph[C[-1]]]
for i in range((K-ct+counter)%(counter)):
    x=stack.pop()
    stack.append(graph[x])

print(stack[0])

Submission status: Wrong Answer

Solution code:
n, k=input().split()
a=input().split()
a=list(map(int,a))
a=list(map(lambda x: x-1,a))
n=int(n)
k=int(k)
cycle=0
now=0

for i in range(n):
  now=a[now]
  cycle+=1
  if now==0:
       break
      
       
k=k%cycle
       
for i in range(k):
       now=a[now]
print(now+1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
k += 1
l1 = list(map(int,input().split()))
l = list(i-1 for i in l1)
mi = [0]
m = l[0]
for i in range(2*(10**5+1)):
  if m in set(mi):
    a = mi.index(m)
    r = mi[a:]
    break
  else:
    mi.append(m)
    m = l[m]
be = mi[:a]+r
#print(be)
if k<= len(be):
  print(be[k])
else:
  w = k-len(be)
  u = w%len(r)-1
  print(r[u]+1)

Submission status: Wrong Answer

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

l = []
used = [0 for _ in range(n)]

c = 0
flag = True
while 1:
    if not flag:
        l.append(c)
    if used[c] == 1 and l:
        break
    if not flag:
        used[c] = 1
    c = a[c]
    flag = False

p = 0
length = len(l)
for i in range(length):
    if l[i] == l[-1]:
        l = l[i:-1]
        p = i
        break

print(l[(k - p - 1) % len(l)] + 1)

Submission status: Wrong Answer

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

mati_check_set = {0}
mati_order = [0]
count = 0
mati = 0
check1, check2 = True, True
while check1 and check2:
    next_town = A[mati] - 1
    count += 1
    if next_town not in mati_check_set:
        mati_check_set.add(next_town)
        mati_order.append(next_town)
        mati = next_town
    else:
        loop = (next_town, mati)
        mati_order.append(next_town)
        check1 = False
        break
    
    if count-1 == K:
        check2 = False
        ans = next_town + 1
        print(ans)

if check1 == False:
    count1 = 0
    check3 = True
    town = 0
    if loop[0] != 0:
        while check3:
            next_town = A[town] - 1
            count1 += 1
            if next_town == loop[0]:
                check3 = False
            town = next_town
        a = count1
        b = len(mati_order) - 2
        c = b - a + 1
        amari = (K - a + 1) % (c + 1)
        index = mati_order.index(loop[0]) + amari
        print(mati_order[index])
    else:
        c = len(mati_order) - 1
        index = K % c
        print(mati_order[index]+1)

Submission status: Wrong Answer

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


tmp = [1]
tele = A[1]
cnt = 0

while True:
    cnt += 1
    if tele in tmp:
#         print('index:', tmp.index(tele))
        tmp2 = tmp[tmp.index(tele):]
        break
        
    tmp.append(tele)
    tele = A[tele]

# print(cnt, tmp, tmp2)
K -= len(tmp) - len(tmp2)
cnt2 = K % len(tmp2)
# print('cnt2:',cnt2)
print(tmp2[cnt2])

Submission status: Wrong Answer

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

towns = [0] * N

town = 1
i = 0
while True:
    if towns[town-1] < 2:
        
        if towns[town-1] == 0:
            i += 1
            
        towns[town-1] += 1
        town = A[town-1]
    else:
        s = town
        break
    
loop = towns.count(2)
i = i - loop
k = (K - i) % loop

if k == 0:
    print(s)
    exit()

for j in range(k):
    town = A[town-1]

print(town)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split(" "))
A = [i for i in map(int, input().split(" "))]

hist = [-1 for i in range(N)]
route = []
loop = []

jump = 0
cur = A[0] - 1
route.append(0)
hist[0] = jump
while hist[cur] == -1:
    jump = jump + 1
    route.append(cur)
    hist[cur] = jump
    cur = A[cur] - 1

loop = route[hist[cur]:]

print(cur, hist, route, loop)

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

Submission status: Wrong Answer

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

exist = [1]
#exist.append(a[0])
ex = {}
ex[1] = 0
#ex[a[0]] = 0

cnt = 1
while(True):
    if a[exist[-1]-1] in ex:        
        idx = exist.index(a[exist[-1]-1])
        exist.append(a[exist[-1]-1])
        break
    ex[a[exist[-1]-1]] = 0
    exist.append(a[exist[-1]-1])
    
    cnt += 1
    if cnt >= k-1:
        print(exist[-1])
        exit()


#k = k-idx
d = (k-idx) % (cnt-idx)

print(exist[d+idx])

Submission status: Wrong Answer

Solution code:
N,K= map(int, input().split())
A = list(map(int, input().split()))
count=0
i=0
while count<=K:
    i=A[i-1]
    count=count+1
print(i)

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))
t=1
C=[1]
D=[]
g=0
s=0
b=0
for i in range(2*N+1):
    t=A[t-1]
    if g==0 and t in C:
        g=i+1
        b=1
    if g==0:
        C.append(t)
    if b==1:
        if t not in D:
            D.append(t)
        else:
            s=len(C)-len(D)
            if s!=0:
                t=(i+1)%s
            else:
                t=1
            break
#print(t) 
if s==0:
    K=K%N
else:
    K=(K-s)%len(D)
for i in range(K+1):
    t=A[t-1]
    #print(t)
print(t)
#print(b,s,K)
#print(C,D)

Submission status: Wrong Answer

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

now = a[0]
if k % n == 0:
    k = n
else:
    k = k % n

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

print(now)

Submission status: Wrong Answer

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

li = [0]
li.extend(list(map(int, input().split())))

def search(town, li, times):
  return 1
  if times == 0:
    return town
  return search(li[town], li, times-1)

tuita = [0]*(n+1)
cnt = 0
town = 1

while True:
  town = li[town]
  cnt += 1
  if tuita[town] == 0:
    tuita[town] = cnt
  else:
    if k < tuita[town]:
      print(search(1, li, k))
    elif k == tuita[town]:
      print(town)
    else:
      print(search(town, li, (k - tuita[town]) % (cnt - tuita[town])))
    break

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
# N, K = 6, 727202214173249351
# A_list = [6, 5, 2, 5, 3, 2]
# N, K = 4, 11
# A_list = [2,3,1,2]
Place = 0
N_list = [0 for i in range(N)]
Count_Start = 0
Count_Stop = 0
while True:
    Count_Start += 1
    if N_list[Place] != 0:
        Count_Stop = Count_Start
        Count_Start = N_list[Place]
        break
    N_list[Place] += Count_Start
    Place = A_list[Place] -1
Loop_Count = Count_Stop - Count_Start
# print(Loop_Count)
K -= (int(K/Loop_Count) -1) * Loop_Count
# print(K)

Place = 0
for i in range(K):
    Place = A_list[Place] - 1
    # print(Place)
print(Place+1)

Submission status: Wrong Answer

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

index = 0
keiro = []
s_keiro = set()
loop_f = False

for i in range(k):
  index = al[index] - 1
  if index in s_keiro:
    start = keiro.index(index)
    mod = i - start
    loop_f = True
    break
  s_keiro.add(index)
  keiro.append(index)

if loop_f:
  pos = (k-start) % mod
  print(keiro[start + pos - 1]+1)
else:
  print(keiro[-1] + 1)

Submission status: Wrong Answer

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

seen = []
count = 0
next_ = 1

while next_ not in seen:
    seen.append(next_)
    next_ = A[next_]
    count += 1

# 位数を求める
init = seen.index(next_)
loop = count - init

resi = (K - init) % loop

for i in range(resi):
    next_ = A[next_]

print(next_)

Submission status: Wrong Answer

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

to_loop = cnt_ls.index(first)
loop_ls = cnt_ls[to_loop:]
loop_num = len(cnt_ls) - to_loop


if k <= to_loop+1:
    print(cnt_ls[k-1])
    exit()
else:
    k -= to_loop

k %= loop_num
print(loop_ls[k])

Submission status: Wrong Answer

Solution code:
N,K= map(int,input().split())
city_list = list(map(int,input().split()))
#city_list = []
rec_list = [0]
'''
for i in range(N):
    city_list.append([i+1,list[i]])
'''
N = 0
while K != 0:
    N = city_list[N] - 1
    if N in rec_list:
        break
    rec_list.append(N)
    K = K -1
count = 0
for i in range(len(rec_list)):
    if rec_list[i] == N:
        break
    count += 1
#print(count,rec_list)
print(rec_list[K%(len(rec_list)-count)+count-1]+1)