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:
#!/usr/bin/env python3
import sys

# 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():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]

    done = [int()]*(N)
    done_k = [0] * N


    i = 0
    q = 1
    while done_k[q-1] == 0:
        done[i] = q
        done_k[q-1] = 1
        i+=1
        q = A[q-1]

    f_q = done.index(q)
    r = i - f_q

    if K <= f_q:
        t = K
    else:
        k = (K - f_q)%r
        t = k + f_q

    print(done[t])        

    # q = A[0]
    # for _ in range(t-1):
    #     q=A[q-1]
    # print(q)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split(' '))
a=list(map(int,input().split(' ')))
loc=1
begin=0
end=0
d={1:0}
for i in range(n+1):
    loc=a[loc-1]
    if loc in d.keys():
        begin=d[loc]
        end=i+1
        break
    d[loc]=i+1
if k<=end:
    end=0
if end==begin+1:
    k=begin
    end=0
if end != 0:
    x=(k-begin+1)%(end-begin)
    if x==0:
        x=end-begin
    k=x+begin-1
loc=1
for _ in range(k):
    loc=a[loc-1]
print(loc)

Submission status: Accepted

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

while True:
    if not A[i]:
        start = i + 1
        break
    s.append(i + 1)
    dest = A[i]
    A[i] = None
    i = dest - 1
    length += 1

if K == 2:
    print(s[1])
elif start == s[0]:
    amari = K % length
    if amari == 0:
        print(s[-1])
    else:
        print(s[amari - 1])
else:
    idx = s.index(start)
    s2 = s[idx:]
    length2 = len(s2)
    tmp = length - length2
    if K < tmp:
        print(s[K-1])
    else:
        K -= tmp
        amari = K % length2

        if amari == 0:
            print(s2[-1])
        else:
            print(s2[amari - 1])

Submission status: Accepted

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回目にどこにいるか
alre=[-1]*n
alre[0]=1
for j in range(1,k+1):
    if tmp==dict[tmp]:
        break
    tmp=dict[tmp]#現在地更新
    if alre[tmp]==-1:#tmp not in num2city.values():#現在地がまだきたことない
        alre[tmp]=1
        num2city[j]=tmp
        city2num[tmp]=j
    else:
        mae=city2num[tmp]
        term=j-mae 
        res=k-j
        r=res%term
  #      print(mae,term,res,r,mae+r,num2city[mae+r])
        tmp=num2city[mae+r]
 #       print(tmp)
        break
   # print(tmp+1)
    
#print(num2city)
#print(city2num)
print(tmp+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
x = 1
step = 0
count = [0]*N
count[0] += 1
memo = [-1]*N
memo[0] = 0
M = K
flag = 0
for i in range(M):
    x = A[x-1]
    count[x-1] += 1
    step += 1
    K -= 1
    if memo[x-1] != -1:
        s = memo[x-1]
        t = step-s
#        print(s,t)
        flag = 1
        break
    memo[x-1] = step
#    print(step,x,count,memo)
if flag == 0:
    print(x)
else:
    if t>= 1:
        K %= t
    else:
        K = 1
    for i in range(K):
        x = A[x-1]
    print(x)

Submission status: Accepted

Solution code:
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

#n = int(stdin.readline().rstrip())
n,k = map(int, stdin.readline().rstrip().split())
A = list(map(int, stdin.readline().rstrip().split()))
#numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
#word = [stdin.readline().rstrip() for _ in range(n)]
#number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
#zeros = [[0] * w for i in range(h)]

# find loop
visited = [0]*n
visited[0] = 1
next = A[0] - 1
loop = 0
v = 0
for i in range(n):
    if visited[next] != 0:
        loop = i-visited[next]+2
        v = i
        break
    else:
        visited[next]= i+2
        next = A[next] - 1

road =  v+1 - loop
# 計算
if k <= road:
    print(visited.index(k+1) + 1)
    exit()
k = k - road
k = k%loop
print(visited.index(k+1+road) +1)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

# 入力
N, K = map(int,input().split()) 
Aori = list(map(int,input().split()))
A = [x-1 for x in Aori]

Arrival = [0]*N
NowTown = 0
Arrival[NowTown] = 1
ArrivalStep = [0]*N

Step = 0

if K <= N:
    for i in range(K):
        NowTown = A[NowTown]
    print(NowTown+1)
    exit()

while True:
    Step += 1
    NowTown = A[NowTown]
    if Arrival[NowTown] == 1:
        break
    ArrivalStep[NowTown] = Step
    Arrival[NowTown] = 1

RoopNumper = Step - ArrivalStep[NowTown]

Rest = K-Step

Rest %= RoopNumper

if Rest == 0:
    print(NowTown+1)
else:
    for i in range(Rest):
        NowTown = A[NowTown]
    print(NowTown+1)

Submission status: Accepted

Solution code:
import sys

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

is_visited = [0] * n
visited = list()
i = 0
cnt = 0
while True:
    if cnt == k:
        print(i+1)
        sys.exit()
    if is_visited[i]:
        break
    is_visited[i] = 1
    visited.append(i)
    i = a[i]
    cnt += 1

si = visited.index(i)
loop = visited[si:]
n_loop = len(loop)
left_k = k - cnt
print(loop[left_k % n_loop] + 1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
check = [-1]*N
cnt = 0
check[0] = cnt
index = A[0]

while True:
    if check[index-1] != -1:
        break
    cnt += 1
    if K-1 == cnt:
        print(A[index-1])
        exit()
    check[index-1] = cnt
    index = A[index-1]

length = cnt - check[index-1] + 1
K -= (len(A) - check.count(-1) -length)
l = []
for _ in range(length):
    l.append(A[index-1])
    index = A[index-1]
ans = K % len(l)
print(l[ans-1])

Submission status: Accepted

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
 
position = 1
exp1 = [0] * n
exp1[0] = 1
exp = [1]
count = 0
 
if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if exp1[position - 1] == 0:
      exp.append(position)
      exp1[position - 1] += 1
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])

Submission status: Accepted

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

next = 1
exist=[0]*n
ans=[]
ans.append(1)


for i in range(n):
    if i+1==k:
        print(a[next-1])
        exit()
    if exist[a[next-1]-1]!=0:
        flag=a[next-1]
        break
    else:
        ans.append(a[next-1])
        exist[next-1]=1
        next=a[next-1]

aa=ans.index(flag)
cycle = len(ans)-aa
po = (k-aa)%cycle

print(ans[po+aa])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
d = {}
for i, a in enumerate(A):
    d[i + 1] = int(a)

l = 1
nxt = d[1]
is_visit = [False for _ in range(n + 1)]
is_visit[1] = 0
while is_visit[nxt] is False:
    is_visit[nxt] = l
    l += 1
    nxt = d[nxt]
c = is_visit[nxt]
lc = l - is_visit[nxt]

if k <= c:
    r = 1
    for _ in range(k):
        r = d[r]
    print(r)
else:
    r = nxt
    m = (k - c) % lc
    for _ in range(m):
        r = d[nxt]
        nxt = d[nxt]
    print(r)

Submission status: Accepted

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
step=0
now=0
ini=0
now2=n
count=[0]*n
count[0]=1

while k>0:
  now=a[now]
  k+=-1
  if count[now]==1:
    ini=now
    while now2!=ini:
      if cycle==0:
        now2=ini
      now2=a[now2]
      cycle+=1
    else:
      k=k%cycle
      for j in range(k):
        now=a[now]
      break
  count[now]=1



       

print(now+1)

Submission status: Accepted

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

leg = [ 0 ] * n
leg[ 0 ] = 0

p = 0
city_old = 1
for x in range( k ):
    city_new = a[ city_old-1 ]
    if leg[ city_new-1 ] == 0 and city_new != 1:
        leg[ city_new-1 ] = x + 1
    else:
        loop = x + 1 - leg[ city_new-1 ]
        modk = ( k - ( x + 1 ) ) % loop
#        print( loop, modk )
        break
    city_old = city_new
    p += 1

if p == k:
    print( city_old )
    exit()


city_old = city_new
for x in range( modk ):
    city_new = a[ city_old-1 ]
    city_old = city_new

print( city_old )

Submission status: Accepted

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(n*10):
    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

h = 1
if k < f:
    for i in range(k):
        h = a[h-1]
    print(h)
else:
    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: Accepted

Solution code:
import sys
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.insert(A, 0, 0)

flg = [False for _ in range(N + 1)]
town = []
i = 1
cnt = 0
for _ in range(N):
    town.append(i)
    flg[i] = True
    i = A[i]

if len(town) >= K:
    print(town[K])
else:
    s = i
    to_s = town.index(s)
    loop = len(town) - to_s
    print(town[(K - to_s) % loop + to_s])

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
 
import numpy as np
 
 
 
Nstock = np.zeros(N)
 
cpos = 1
Nstock[cpos - 1] = 1
stock = [cpos]
loop = []
 
idx = 0
for i in range(K):
    cpos = A[cpos-1]
    if Nstock[cpos - 1]  == 1:
        idx = stock.index(cpos)
        loop = stock[idx:]
        break
    Nstock[cpos - 1] = 1
    stock.append(cpos)
    
if loop != []:
    v = (K - idx) 
    a = v %len(loop)
    print(loop[a])
else:
    print(stock[K])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

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

    his = [0] * (N+1)
    s = 1
    cnt = 1
    his[1] = 1
    while his[A[s]] == 0:
        s = A[s]
        cnt += 1
        his[s] = cnt


    if K >= cnt:
        s = A[s]
        cnt -= his[s] - 1

        k = (K - his[s] + 1) % cnt
    else:
        k = K
        s = 1
    for i in range(k):
        s = A[s]
    print(s)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

town_dict = dict()
for a,town in enumerate(town_list, 1):
    town_dict[a] = town


if k <= n:
    now_place = 1
    for _ in range(k):
        now_place = town_dict[now_place]

    print(now_place)

if k > n:
    now_place = 1
    visit_town = dict()
    visit_town[1] = 0
    tmp_last_visit = -1
    tmp_visit = -1
    for j in range(n):
        now_place = town_dict[now_place]

        if now_place in visit_town:
            tmp_last_visit = visit_town[now_place]
            tmp_visit = j+1
            break

        visit_town[now_place] = j+1

    if tmp_last_visit == -1:
        print(now_place)
    else:
        ans = (k-tmp_visit)%(tmp_visit-tmp_last_visit)
        
        for _ in range(ans):
            now_place = town_dict[now_place]

        print(now_place)

Submission status: Accepted

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

here = 1
log = [1]
loop = []
num_log = [0] * (n + 1)
num_log[1] = 1
for i in range(k):
    here = A[here]
    if num_log[here] == 1:
        pre_loop = log.index(here)
        k = k - pre_loop
        loop = log[pre_loop:]
        here = loop[k % len(loop)]
        break
    else:
        num_log[here] = 1
    log += [here]
print(here)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

used = [-1]*n

now = 0
tmp = 0
while True:
    used[now] = tmp
    now = a[now]
    tmp += 1
    if tmp == k:
        print(now+1)
        exit()    
    if used[now] != -1:
        break

k -= tmp
tank = []
p = now
while True:
    tank.append(p)
    p = a[p]
    if p == now:
        break

print(tank[k%len(tank)]+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,k=map(int,input().split())
a=list(map(int,input().split()))
seen=[False]*n
l=[1]
now=1
while 1:
    now=a[l[-1]-1]
    l.append(now)
    if seen[now-1]:
        break
    seen[now-1]=True
now=l[-1]
until=l.index(now)
if until>k:
    print(l[k])
    sys.exit()
k-=until
loop=len(l[until:-1])
#print(l)
k%=loop
print(l[until+k])
#print(l)
#print(until,now)

Submission status: Accepted

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

li = [0]
li.extend(list(map(int, input().split())))
tuita = [0]*(n+1)
cnt = 0
town = 1

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

town = lastTown
while times > 0:
  if times <= 0:
    break
  times -= 1
  town = li[town]
print(town)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
x = [1]
y = [False]*n
i = 0
s = 0
t = 0
xa = x.append
while True:
  if y[i] == True:
    for j in range(len(x)):
      if i == x[j]-1:
        s = j
        t = len(x)-j-1
        break
    break
  else:
    y[i] = True
    xa(a[i])
    i = a[i]-1
if k < s:
  print(x[k])
  exit()
x = x[s:-1]
print(x[(k-s)%t])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = []
check = {}
key = -1
p = 0
c = 0
t = 0
while True:
    ans.append(p)
    check[p] = 0
    p = a[p]-1
    c += 1
    if c == k:
        print(p+1)
        t = 1
        break
    if p in check:
        key = ans.index(p)
        break
if t == 0:
    if len(ans) == 1:
        print(a[0])
    else:
        r = ans[key:]
        mod = (k-key)%len(r)
        if mod == 0:
            print(r[0]+1)
        else:
            print(r[mod]+1)
#print(r[mod]+1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = [i -1 for i in map(int,input().split())]
ss = set([])
point = 0
for i in range(N):
    if point in ss:
        break
    ss.add(point)
    point = P[point]
S = [0]
points = 0
for i in range(len(ss)-1):
    points = P[points]
    S.append(points)
loop = S[S.index(point):]
ll = len(S)
l = len(loop)
if ll > M:
    print(S[M]+1)
elif ll == M:
    print(point+1)
else:
    print(loop[(M-ll)%l]+1)

Submission status: Accepted

Solution code:
import sys

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

i = 1
l = [1] * N
s = set([1])
n = 1
while True:
    n = A[n-1]
    if n in s:
        l = l[:i]
        mod = i - l.index(n)
        init_len = l.index(n)
        break
    else:
        l[i] = n
        s.add(n)
        i += 1

if K < init_len:
    print(l[K])
else:
    rest = ((K-init_len) % mod)
    print(l[init_len+rest])

Submission status: Accepted

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

#足跡
footprint=[0]*n

omoide=[]
now=0
counter=1
while True:
    if footprint[now]!=0:
        break
    footprint[now]=counter
    omoide.append(now)
    goto=alist[now]-1
    now=goto
    counter+=1

joso=footprint[now]-1
shuki=counter-footprint[now]

if k>joso:
    k-=joso
    k=k%shuki

    ans=omoide[joso+k]+1

else:
    ans=omoide[k]+1
    
print(ans)

Submission status: Accepted

Solution code:
from time import time
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
L = [-1 for i in range(N)]

visited = []
now = 0
loopstarts = None
looplength = None
t0 = time()

for i in range(N):
    if L[now] != -1:
        break
    else:
        L[now] = i
        visited.append(now)
        now = A[now]-1

loopstarts = visited.index(now)
looplength = len(visited)-loopstarts

if K < loopstarts:
    print(visited[K]+1)
else:
    print(visited[loopstarts+(K-loopstarts)%looplength]+1)
# print(time()-t0)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
mati=list(map(int,input().split()))
count=0
i=mati[0]
matidic={}
frag=1
while frag:
    count+=1

    if i in matidic:
        frag=0
        bef=matidic[i]
        roop=count-bef

    else:
        matidic[i]=count
    i = mati[i - 1]

#print(roop,bef,matidic)
#print(k%roop)
if bef<k:
    ans=[i for i,j in matidic.items() if j==(k-bef)%roop+bef]
else:
    ans=[i for i,j in matidic.items() if j==k]
print(ans[0])

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

tele = list(input().split())
tele = np.array([int(tele[i]) for i in range(N)])
seen = set([])
roop_in = deque([])
now = 1
w_num = 0

while now not in seen and w_num < K:
    seen.add(now)
    roop_in.append(now)
    now = tele[now - 1]
    w_num += 1

if w_num == K:
    print(now)
else:
    roop_in_index = roop_in.index(now)
    roop = list(roop_in)[roop_in_index:]
    roop_len = len(roop)
    last = (K - (w_num - 1)) % roop_len
    print(roop[last - 1])

Submission status: Accepted

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

used = [False]*(N+1)
ls = []
key = []
k = 1
while True:
    ls.append(k)
    used[k] = True
    k = Als[k]
    if used[k]== True:
        key.append(k)
        break
#k回移動した先が入る

kind= ls.index(key[0]) 
if K <= kind:
    print(ls[K])
else:
    K = K - kind
    ls = ls[kind:]
    mn = K % len(ls)
    print(ls[mn])

Submission status: Accepted

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 = []
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
if i >= K:
    print(tele_lis[K])
else:
    print(tele_lis[i::][(K-i) % (sum(check)-i)])

Submission status: Accepted

Solution code:
import collections

def main():
    n, k = map(int, input().split())
    a = [int(i) - 1 for i in input().split()]
    ans = solve(n, k, a)
    print(ans)


def solve(n, k, a):
    arrived = [-1 for i in range(n)]
    path = collections.deque()

    cnt = 0
    pos = 0
    path.append(pos)
    arrived[pos] = cnt

    while True:
        cnt += 1
        pos = a[pos]
        if arrived[pos] != -1:
            break
        arrived[pos] = cnt
        path.append(pos)
        if cnt == k:
            return pos + 1

    while True:
        if path[0] == pos:
            break
        path.popleft()

    #print(f'{path}')
    #print(f'{arrived[pos]}')

    path = list(path)
    k -= arrived[pos]

    ans = path[k % len(path)]

    return ans + 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N, K = ri_()
A = ri_()
d = [0] * N
d[0] = 1
cnt = 1
loop = 0
now = 0
while True:
    now = A[now] - 1
    if d[now]:
        loop = cnt - d[now] + 1
        break
    else:
        cnt += 1
        d[now] = cnt
ans = 0
for i in range(N):
    if d[i] == min(d[now] + (K - cnt) % loop, K + 1):
        ans = i + 1
print(ans)

Submission status: Accepted

Solution code:
# Problem D - Teleporter

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

# initialization
visit_list = [0]*N
visit_list[0] = 1
pos = a_nums[0]
visit_count = 1

while visit_list[pos-1]==0 and visit_count<K:
    visit_count += 1
    visit_list[pos-1] = visit_count
    pos = a_nums[pos-1]
visit_count += 1

# calc 1
if visit_count<K:
    tmp_1 = 0
    if pos==1:
        tmp_1 = visit_count - visit_list[pos-1] # 周期
    else:
        tmp_1 = visit_count - visit_list[pos-1]
    tmp_2 = (K-visit_count) % tmp_1 # 何周するのか
    # tmp_2回分ループ処理を行う
    for i in range(tmp_2+1):
        pos = a_nums[pos-1]

# output
print(pos)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = [0]
    ta = list(map(int, input().split()))
    a += ta
    kaiten = [0] * (n + 1)
    count = 0
    koko = 1
    kaitenkikan = 0
    while k > 0:
        koko = a[koko]
        count += 1
        k -= 1
        if kaiten[koko] > 0:
            kaitenkikan = abs(count - kaiten[koko])
            break
        else:
            kaiten[koko] = count
    if k == 0:
        print(koko)
        sys.exit()
    k_remain = k % kaitenkikan
    if k_remain < 0:
        k_remain += kaitenkikan

    while k_remain > 0:
        koko = a[koko]
        k_remain -= 1

    print(koko)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

flag = [0 for _ in range(N)]

tmp = 1
i = 1
flag[0] = 1
while(True):
    tmp = A[tmp-1]
    i += 1
    if (flag[tmp-1] != 0):
        break
    flag[tmp-1] = i

pre = flag[tmp-1] - 1
cyc = i - flag[tmp-1]
if (K >= pre):
    index = (K - pre) % cyc
    if (index == 0):
        print(A[flag.index(pre + cyc)])
    else:
        print(A[flag.index(pre+index)])
else:
    print(A[flag.index(K)])

Submission status: Accepted

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

visited = [-1] * N
visited[0] = 0
nxt = 1
cycl = N
m = 0
for i in range(N):
    nxt = A[nxt-1]
    if visited[nxt-1] == -1:
        visited[nxt-1] = i+1
    else:
        cycl = i + 1 - visited[nxt-1]
        m = visited[nxt-1]
        break
if K < m: k = K
else:
    k = (K - m) % cycl + m

for i in range(N):
    if visited[i] == k:
        print(i+1)
        break

Submission status: Accepted

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

if K >= 2*N:
    point = 0
    L = [0 for _ in range(N)]
    loop = []
    for i in range(N+1):
        L[point] +=1
        T = 1
        if L[point] == 2:
            loop.append(point)
            p = point
            for j in range(N+1):
                point = A[point]
                if point != p:
                    loop.append(point)
                else:
                    T = 0
                    break
        if T == 1:
            point = A[point]
        else:
            break
    c = 0
    p = 0
    for i in range(N):
        if p != loop[0]:
            c+=1
            p = A[p]
        else:
            break
    J = K-c
    n = len(loop)
    k = J%n
    print(loop[k]+1)
else:
    point = 0
    for i in range(K):
        point = A[point]
    print(point+1)

Submission status: Accepted

Solution code:
from sys import stdin
import sys

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = list(map(int, input().split()))
B = [i for i in range(1, N+1)]
d = dict(zip(B, A))
t = [0 for i in range(N)]
d1 = dict(zip(B, t))
temp = 1
cnt = 0
ans = []
for i in range(K):
    d1[d[temp]] = d1.get(d[temp], 0)+1
    if d1.get(d[temp], 0) == 2:
        cnt += 1
        ans.append(d[temp])
        # print(i, d[temp])
    if d1.get(d[temp], 0) == 3:
        break
    temp = d[temp]
    if i == K-1:
        print(temp)
        sys.exit()
cnt1 = 0
for i, v in enumerate(d1):
    if d1[v] == 1:
        cnt1 += 1
# print(cnt, cnt1, d1, temp, ans)
k = K-1-cnt1
print(ans[k % cnt])

Submission status: Accepted

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

visited = [1] + [0]*(n-1)
idx = [0] + [-1]*(n-1)
route = [0]
while True:
    now = a[route[-1]]
    if visited[now]:
        break
    visited[now] = 1
    idx[now] = len(route)
    route.append(now)

border = idx[a[route[-1]]]
non_loop = route[:border]
loop = route[border:]

print(non_loop[k]+1) if k < len(non_loop) else print(loop[(k-len(non_loop))%len(loop)]+1)

Submission status: Accepted

Solution code:
import bisect
N,K=map(int,input().split())
A=list(map(int,input().split()))
index=[0]
index.append(A[0]-1)
tt=[A[0]-1]
flag=0
count=0
for _ in range(1,K):
    t=index[-1]
    ttt=bisect.bisect_left(tt, A[t]-1)

    if len(tt) > ttt and tt[ttt]==A[t]-1:
        index.append(A[t]-1)
        flag=1
        break
    index.append(A[t]-1)
    bisect.insort(tt,A[t]-1)
if flag==0:
    print(index[-1]+1)
    exit()
#print("a")
#print(index)
check = index[-1]
for i,c in enumerate(index):
    if c==check:
        a_path=i
        break
K-=a_path
t=len(index)-1-a_path
print(index[a_path+K%t]+1)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(lambda x: x-1, map(int, input().split())))
T = [False]*N

initcount = 0
count = 0
cur = 0
for _ in range(N):
    count += 1
    T[cur] = True
    cur = A[cur]
    if T[cur]:
        break
initcur = 0
for _ in range(count+1):
    initcount += 1
    initcur = A[initcur]
    if initcur == cur:
        break
if count != initcount:
    count -= initcount

if K <= initcount:
    cur = 0
    for _ in range(K):
        cur = A[cur]
    print(cur+1)
else:
    K -= initcount
    count = K%count
    for _ in range(count):
        cur = A[cur]
    print(cur+1)

Submission status: Accepted

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

check = [-1] * n
now = 0
check[now] = 0
cnt = 0
while cnt < k:
    cnt += 1
    now = g[now]
    if check[now] != -1:
        sa = cnt - check[now]
        cnt = cnt + (k - cnt)//sa *sa
    else:
        check[now] = cnt
print(now+1)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
c = {}
c[1] = 0
n = 0
k = 1
while c.get(A[k]) is None or c[A[k]] != 2:
    if c.get(A[k]) is None:
        c[A[k]] = 0
    else:
        c[A[k]] += 1
    n += 1
    k = A[k]

from collections import Counter
if n <= K:
    num = Counter(c.values())[2]
    sa = len(c)-num
    bbb = K - sa
    m = bbb % num
    abc = list(c.keys())
    abc = abc[sa:len(c)]
    print(abc[m])
else:
    a = 1
    for i in range(K):
        a = A[a]
    print(a)

Submission status: Accepted

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

city = [-1 for i in range(0,N,1)]#0~N-1
count = 0
nex_city = 0
city[0]=0
while True:
    city[nex_city] = count
    nex_city = A[nex_city]-1
    count+=1
    if city[nex_city] >= 0:
        break

X = city[nex_city]
Y = count - city[nex_city]

nex_city = 0
if K < X:
    for i in range(0,K,1):
        nex_city = A[nex_city]-1
    print(nex_city+1)
    exit()

nex_city = 0
for i in range(0,X+(K-X)%Y,1):
    nex_city = A[nex_city]-1
print(nex_city+1)

Submission status: Accepted

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)
cnt=0
while flag==0 and cnt<k:
    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]
        break
    cnt+=1
if cnt==k:
    print(bef)
    exit()
for j in range(len(town)):
    if town[j]==memo:
        num=j
        break
x=len(town)-num
y=(k-num)%x
print(town[num+y])

Submission status: Accepted

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

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

genzaiti=0
visited=[-1]*n
visited[0]=0
nikaime=0
for i in range(k):
    genzaiti=A[genzaiti]-1
    if visited[genzaiti]==-1:
        visited[genzaiti]=i+1 # i+1回目で訪れた
    else:
        nikaime=i+1
        break

if nikaime==0:
    print(genzaiti+1)
else:
    k=k-nikaime # nokori
    idx=[i for i, v in enumerate(visited) if v>=visited[genzaiti]]
    aaa=[]
    for i in idx:
        aaa.append([i,visited[i]])
    aaa.sort(key=lambda x:x[1])
    finalidx=k%len(aaa)
    
    print(aaa[finalidx][0]+1)

Submission status: Accepted

Solution code:
N, K = (int(x) for x in input().split())
list = list(int(x) for x in input().split())
now = 1
check = [0]*N
begin = 1
begin_len = 0
for i in range(N):
    check[now-1] = i
    now = list[now-1]
    # ループ検証
    if check[now-1] != 0:
        begin = now
        begin_len = check[now-1]
        loop = (i+1) - check[now-1]
        break
# print(begin)
# print(begin_len)
# print(loop)
if K <= (begin_len+loop):
    now = 1
    for i in range(K):
        now = list[now-1]
else:
    now = begin
    Ka = (K-begin_len) % loop
    for i in range(Ka):
        now = list[now-1]
print(now)