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:
n,k=map(int,input().split())
a=tuple(map(int,input().split()))
flag=[-1]*n
flag[0]=0
x,count=1,0
for i in range(1,n+1):
  x=a[x-1]
  if flag[x-1]<0:
    flag[x-1]=i
  else:
    l=i-flag[x-1]
    count=flag[x-1]
    break
if count>=k:
  x=1
  for _ in range(k):
    x=a[x-1]
  print(x)
  exit()
k=(k-count)%l
for _ in range(k):
  x=a[x-1]
print(x)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
P = [-1] * N 
cur = 0
P[cur] = 0
route = [1]

for step in range(K):
  cur = A[cur]
  route.append(cur + 1)
  if P[cur] >= 0:
    l_start = P[cur]
    l_end = step + 1
    l_len = l_end - l_start
    break
  else:
    P[cur] = step + 1
else:
  print(cur + 1)
  quit()

print(route[l_start + ((K - l_start) % l_len)])

Submission status: Accepted

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

current = 1
N_counter = [0] * N 
N_counter_idx = [0] * N 
N_counter[current-1] += 1
N_counter_idx[current-1] = 1

k_reserved = -1
for i in range(1, N+1):
    current = A[current-1]
    N_counter[current-1] += 1
    if i == K:
        k_reserved = current
    if N_counter[current-1] == 2:
        break
    N_counter_idx[current-1] = i+1

if K < i:
    print(k_reserved)
else:
    #print(N_counter)
    #print(N_counter_idx)
    pre_loop_length = N_counter_idx[current-1] - 1
    loop_length = max(N_counter_idx) - pre_loop_length
    #print(pre_loop_length)
    #print(loop_length)
    K_new = (K - pre_loop_length) % loop_length + pre_loop_length
    
    # K_new = K - (K // i) * i 
    current = 1
    for k in range(K_new):
        current = A[current-1]
    print(current)

Submission status: Accepted

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

idx = 0
stp = 0
ans = 0
while(True):
  stp += 1
  idx = A[idx] - 1
  if c[idx]==0 and idx!=0:
    c[idx] = stp
  else:
    tmp1 = c[idx]
    tmp2 = stp - tmp1
    break
  if stp>=K:
    ans = idx + 1
    break

if(ans>0):
  print(ans)
else:
  k1 = K - tmp1
  k2 = k1%tmp2
  for _ in range(k2):
    idx = A[idx] - 1
  print(idx+1)

Submission status: Accepted

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

# ループを見つけに行けばイ


def loop(now, town):
    cnt = 0
    while True:
        #print(now)
        next = a[now]
        if town[next] == 1:
            cnt += 1
            break
        else:
            town[next] = 1
            now = next
            cnt += 1
    return cnt, next


def tp(num, now):
    for _ in range(num):
        next = a[now]
        now = next
    return next


town1 = [None] + [0] * n
town1[1] = 1
loop1, now1 = loop(1, town1)

town2 = [None] + [0] * n
town2[now1] = 1
loop2, now2 = loop(now1, town2)

if k <= loop1 + loop2:
    ans = tp(k, 1)
else:
    k -= loop1
    k %= loop2
    #print(now1,now2)
    if k == 0:
        ans = now2
    else:
        ans = tp(k, now2)

print(ans)

Submission status: Accepted

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):
    if i + 1 == K:
        print(A[pos])
        exit()
    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: Accepted

Solution code:
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
ans = 1
n = 1
check = 1
city = [-1 for i in range(N+1)]
city[1] = 0
roop = 1
i = 0
while(check == 1):
  if i == K:
    check = 0
  else:
    n = A[n]
    i = i + 1 
    if city[n] == -1:
      city[n] = i
    else:
      roop = i - city[n]
      check = 0
roop_num = (K - i)%roop
for i in range(roop_num):
  n = A[n]
print(n)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [-1] + [int(i) for i in input().split()]
deta = [False for i in range(N+1)]
i = 1
tele = 1
telelist = [1]
while not deta[A[i]]:
    telelist.append(A[i])
    deta[A[i]] = True
    i = A[i]

k = 0
for s in telelist:
    if s == A[i]:
        break
    k += 1
if K<=k:
    print(telelist[K])
else:
    l = len(telelist)-k
    K -= k
    s = K%l
    print(telelist[k+s])

Submission status: Accepted

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
if k == 1:
    print(a[0])
    exit()

cnt = 0
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-1 >= k-1:
        print(exist[-1])
        exit()


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

print(exist[d+idx])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
idx_appearence = [False] * n
idx_appearence[0] = True
arrival_idx = a[0] - 1
idx_appearence[arrival_idx] = True
idx_lst = [0, arrival_idx]
if k <= n:
    for i in range(max(0, k-1)):
        arrival_idx = a[arrival_idx] - 1
    print(arrival_idx + 1)
else:
    for i in range(min(k, n)):
        arrival_idx = a[arrival_idx] - 1
        if idx_appearence[arrival_idx] == False:
            idx_lst.append(arrival_idx)
            idx_appearence[arrival_idx] = True
        else:
            idx_lst.append(arrival_idx)
            break
    former_part_len = idx_lst.index(idx_lst[-1])
    recursive_len = len(idx_lst) - 1 - former_part_len
    print(idx_lst[former_part_len + ((k - former_part_len) % recursive_len)] + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,K=map(int,input().split())
L=list(map(int,input().split()))
L.insert(0,-1)
path=[1]
ind=0
count=0
x=1
t=-1
flag=False
Hash=defaultdict(lambda:0)
for i in range(N+1):
    ne=L[x]
    if Hash[ne]:
        flag=True
        t=Hash[ne]
        break
    path.append(ne)
    ind+=1
    Hash[ne]=ind
    x=ne
if flag==True:
    loop=path[t::]
    if K<(len(path)):
        print(path[K])
    else:
        K=K-len(path)
        K=K%len(loop)
        print(loop[K])
else:
    print(path[K-1])

Submission status: Accepted

Solution code:
N,K = map(int,input().split(" "))
A = list(map(int,input().split(" ")))
A.insert(0,0)
rireki = [1]
counter = 1
now = 1
flag = [0 for _ in range(N + 1)]
flag[1] = 1
while(flag[A[now]] == 0):
    counter += 1
    rireki.append(A[now])
    flag[A[now]] = counter
    now = A[now]
if K < flag[A[now]]:
    print(rireki[K])
else:
    K += counter - (flag[A[now]] - 1)
    K -= flag[A[now]] - 1
    K %= counter - (flag[A[now]] - 1)
    print(rireki[flag[A[now]]- 1 + K])

Submission status: Accepted

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

a = [0] + a
now = 1
cities = [now]
done = set()
done.add(now)
for i in range(n):
    now = a[now]
    if now in done:
        break
    done.add(now)
    cities.append(now)
idx_s = cities.index(now)
# print(idx_s)
f = (len(cities) - idx_s)
# print(f)
if k > idx_s:
    d = k - idx_s
    idx = d%f
    ans = cities[idx + idx_s]
    print(ans)
else:
    print(cities[k])

Submission status: Accepted

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

done = [0]*N
now = 0
cnt = 1
while True:
    if done[now] != 0:
        start = done[now] - 1
        cycle = cnt - start - 1
        break
    else:
        done[now] = cnt
        now = A[now]-1
        cnt += 1
if K>=start:
    K -= start
    K %= cycle
else:
    now = 0
for _ in range(K):
    now = A[now]-1
print(now+1)

Submission status: Accepted

Solution code:


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

ne=0
his=[None for i in range(n)]
l=False
for i in range(min(n,k)):
    if his[ne]!=None:
        back=his[ne]
        loop=i-back
        l=True
        break
    his[ne]=i
    #his.append(ne)
    ne=a[ne]-1

if l:
    ansidx=(k-back)%loop+back
    ans=his.index(ansidx)+1
else:
    ans=ne+1
print(ans)

Submission status: Accepted

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1
b = [0]
flags = [-1]*n
flags[0] = 0
i = 0
while i <= n:
    c = a[b[i]]
    if flags[c] > -1:
        i += 1
        break
    else:
        i += 1
        b.append(c)
        flags[c] = i
if k <= i-1:
    for j in range(len(b)):
        b[j] += 1
    print(b[k])
else:
    #print(b)
    #print(c)
    #print(i)
    #print(flags)
    sb = i - flags[c]
    md = (k - flags[c]) % sb
    for j in range(len(b)):
        b[j] += 1
    print(b[flags[c]+md])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()
for i in range(n):
    a[i] -= 1
ct = [0 for i in range(n)]
seen = [False] * n
def dfs(v):
    nv = a[v]
    seen[v] = True
    if ct[v] + 1 == k:
        return nv, 0
    elif seen[nv]:
        loop = ct[v] - ct[nv] + 1
        res = (k - ct[v] - 1) % loop
        return nv, res
    else:
        ct[nv] = ct[v] + 1
        return dfs(nv)

nv, res = dfs(0)
for i in range(res):
    nv = a[nv]
print(nv + 1)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    n,k = map(int,stdin.readline().rstrip().split())
    As = list(map(int,stdin.readline().rstrip().split()))
    As = [0]+As
    g = set({1})
    l = [0,1]
    now = 1
    i = 0
    while True:
        i+=1
        now = As[now]
        if now in g:
            j = l.index(now)
            print(l[j+(k-i)%(i+1-j)])
            break
            
        else:
            g.add(now)
            l.append(now)
        
        if i == k:
            print(now)
            break
main()

Submission status: Accepted

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

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

visitset = set()
visitcount = dict()
n_point = dict()

x = 1
count = 0
while(x not in visitset):
  visitset.add(x)
  visitcount[x] = count
  n_point[count] = x
  x = A[x-1]
  count += 1


period = count - visitcount[x]

if (K < visitcount[x]):
  print(n_point[K])
else:
  y = (K-visitcount[x]) % period
  print(n_point[visitcount[x] + y])

Submission status: Accepted

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

i = 0
checked = [0 for _ in range(N)]
c = 0
while checked[i] == 0:
  c += 1
  checked[i] = c
  i = An[i] - 1
if checked[i] >= K:
  i = 0
  for k in range(K):
    i = An[i] - 1
  print(i + 1)
else:
  period = c - checked[i] + 1
  diff = K - checked[i] + 1
  mod_diff = diff % period
  for k in range(mod_diff):
    i = An[i] - 1
  print(i + 1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
z = 0
b = [1]
c = [0]*n
for i in range(n*3):
  j = [a[b[i]-1]]
  b.extend(j)
  c[a[b[i]-1]-1] = c[a[b[i]-1]-1]+1
  if c[a[b[i]-1]-1] == 2:
    z = z + 1
if k <= n:
  y = b[k]
else:
  l = (k-n)%z
  y = b[n+l]
print(y)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A_list = list(map(int,input().split()))
# roopがあるときはその範囲

roop = N
first = 0
now = 1
already = [1]
for i in range(N):
  go_town = A_list[now-1]
  already.append(go_town)
  now = go_town

set_A = set(already)
for i in range(len(set_A)+1):
  try:
    set_A.remove(already[i])
  except KeyError:
    first = already.index(already[i])
    roop = already[first:i]
    break

if K < first:
  print(already[K])
else:
  real_K = (K - first) % len(roop)
  print(roop[real_K])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    visited=[1]+[0]*(n-1)
    vil=[0]*(n*10)

    nowi=1
    cnt=1
    while True:
        nxti=A[nowi-1]-1 #0ind
        cnt+=1
        if visited[nxti]==0:
            visited[nxti]=cnt
            vil[cnt-1]=nxti
            nowi=nxti+1 # 1ind
        else:
            prime=visited[nxti]
            loop=cnt-visited[nxti]
            break
    
    if k<=prime:
        print(vil[k]+1)
    else:
        mod=((k+1)-(prime-1))%loop
        if mod==0:
            mod=loop
        print(vil[prime-2+mod]+1)
    

    

    
resolve()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, K = iim()
    A = list(iim())

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

        print(pos)
        return

    dp = [-1]*N
    dp1 = [0]*N
    for i in range(N):
        if dp[pos-1] >= 0:
            lp = i - dp[pos-1]
            i0 = i - lp
            print(dp1[i0:][(K-i0) % lp])
            return
        dp1[i] = pos
        dp[pos-1] = i
        pos = A[pos-1]



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import numpy as np

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

a_dict = {}
for from_a, to_a in enumerate(a_list):
    a_dict[from_a+1] = to_a

now = 1
a_route = [now]
a_set = set([now])
for _ in range(len(a_dict.keys())):
    now = a_dict[now]
    if now in a_set:
        start_c = now
        break
    a_set.add(now)
    a_route.append(now)
a_route = np.array(a_route)

ind = np.where(a_route==start_c)[0][0]
first_path = a_route[:ind]
a_route = a_route[ind:]

if k<=len(first_path)-1:
    print(first_path[k])
else:
    k -= len(first_path)
    print(a_route[k%len(a_route)])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 10 21:34:02 2020

@author: shinba
"""
import sys
sys.setrecursionlimit(500000)

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

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

data = [0]*n
data[0] = 1

li = [0]

while k > 0:
    b = a[li[-1]]-1
    if data[b] == 0:
        data[b] = 1
        li.append(b)
        k -= 1
    else:
        break

if k != 0:
    for i in range(len(li)-1,-1,-1):
        if li[i] == b:
            s = i
            break
    newli = li[s:]
    l = (k-1) % len(newli)
    print(newli[l]+1)
else:
    print(li[-1]+1)

Submission status: Accepted

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

dist = A[0]
visited = {1}
_v = [1]
stop = 0
while True:
    if dist in visited:
        stop = dist
        break
    visited.add(dist)
    _v.append(dist)
    dist = A[dist-1]

made = 0
l = len(_v)
for i in range(l):
    if _v[i] == stop:
        break
    made += 1

# print(stop)
# print(loop)
# print(made)
# print(_v)

if K <= made:
    print(_v[K])
else:
    loop = l - made
    _v = _v[made:]
    K -= made
    K %= loop
    print(_v[K])

Submission status: Accepted

Solution code:

N, K = map(int, input().split())
A = list(map(int, input().split()))
P = set([1])
Q = [1]
loop_st = 0
r = 0
i = 0

for _ in range(N):
  if A[i] not in P:
    P.add(A[i])
    Q.append(A[i])
    i = A[i] - 1
  else:
    loop_st = A[i]
    break

s = Q.index(loop_st)
loop_len = len(Q) - s

if K < s:
  print(Q[K])
else:
  r = (K - s) % loop_len
  print(Q[s+r])

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())
town = [0]*n
tmp_posi = 0

for i in range(n):
    tmp_posi = a[tmp_posi] - 1
    if i+1 == k:
        print(tmp_posi+1)
        exit()
    if town[tmp_posi]:
        first = town[tmp_posi]
        mod = i+1 - first
        k_ = k - first
        break
    else:
        town[tmp_posi] = i+1

cicle = [ [i,t] for i, t in enumerate(town) if t >= first]
cicle = sorted(cicle, key = lambda x:x[1])

print(cicle[k_ % mod][0]+1)

Submission status: Accepted

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

passed = [-1 for _ in range(n)]

cnt = 0
now = 0
_next = a[now]
remain = 0
for i in range(k):
    _next = a[now]
    if passed[_next] != -1:
        pre = passed[_next]
        remain = (k-pre) % (cnt + 1 - pre)
        now = _next
        break
    passed[now] = cnt
    now = _next
    cnt += 1

for _ in range(remain):
    now = a[now]

print(now + 1)

Submission status: Accepted

Solution code:


def solve():
    hm = {}
    steps = k
    curr = 0
    loopsize = 0
    pre = 0
    while not str(curr) in hm and steps > 0:
        hm[str(curr)] = pre
        pre+=1
        curr = a[curr] - 1
        steps -= 1
        loopsize += 1
    if str(curr) in hm:
        loopsize -= hm[str(curr)]
    steps %= loopsize
    while steps > 0:
        curr = a[curr] - 1
        steps -= 1
    print(curr + 1)
    return



n, k = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    visited=[0]*n
    now=0
    visited[0]=1
    route=[0]
    while True:
        next=A[now]-1
        if visited[next]==1:
            break
        else:
            visited[next]=1
            now=next
            route.append(now)
    i=0
    while True:
        if route[i]==next:
            break
        else:
            i+=1
    loop=len(route)-i
    if k<=i:
        print(route[k]+1)
    else:
        k=(k-i)%loop
        print(route[i+k]+1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
cur = 0
reach = [False]*n
x = []
for i in range(k+1):
    x.append(cur)
    if reach[cur]:
        break
    reach[cur]=True
    cur = a[cur]-1
cnt = 0
for i in range(len(x)):
    if x[i]==x[-1]:
        break
    cnt += 1


y = x[cnt:-1]
if k>cnt:
    ind = (k-cnt)%len(y)
    print(y[ind]+1)
else:
    print(x[k]+1)

Submission status: Accepted

Solution code:
(N,K) = map(int,input().split())
A = list(map(int,input().split()))
route = [1]
App = [0]*N
past = 1
for i in range(K):
    past = A[past-1]
    if App[past-1]==1:
        loop = (route.index(past),i+1)
        flag = 0
        break
    else:
        App[past-1] = 1
        flag = 1
        route.append(past)
if flag == 1:
    print(route[-1])
else:
    print(route[loop[0]+(K-loop[0])%(loop[1]-loop[0])])

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
b[1]=0  #町のリストで，何回目で初めて訪れたか
c=a[0]
d=[0]*min(k+1,10**7)
d[0]=1  #i回目の移動でどこにいるかを記録
for i in range(1,k+1):
    d[i]=c
    if b[c]!=-1:
        # print(i,c,b[c])
        print(d[b[c]+(k-b[c])%(i-b[c])])
        exit()
    b[c]=i    
    c=a[c-1]
print(d[-1])

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n , k = IN()
	#s = input()
	al = LIN()
	pre_aa = [-1]*n
	pos = 0
	pre_aa[0]=0
	for i in range(1, k+1):
		pos = al[pos]-1
		if pre_aa[pos] >= 0:
			loop = i - pre_aa[pos]
			break
		pre_aa[pos] = i
	else:
		return pos + 1
	
	#pa((k,i,loop))
	for _ in range((k - i) % loop):
		pos = al[pos]-1
	
	print(pos + 1)
	
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

for i, v in enumerate(a):
    g[i+1] = v

def find_num(target):
    path = 1
    target_ = g[target]
    while target_ != target:
        target_ = g[target_]
        path += 1
    return path

target = 1
visited = dict()
flag = False
for i in range(k):
    target = g[target]
    if target not in visited:
        visited[target] = True
    else:
        p = find_num(target)
        flag = True
        break
if flag:
    for _ in range((k-1-i)%p):
        target = g[target]
    print(target)
else:
    print(target)

Submission status: Accepted

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

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    t = 1
    visited = [-1] * (n+1)
    visited[1] = 0
    t_list = [1]
    i = 0

    while k > 0:
        i += 1
        k -= 1
        t = a[t-1]
        if visited[t] == -1:
            visited[t] = i
            t_list.append(t)
        else:
            loop = t_list[visited[t]:]
            l = len(loop)
            break

    if k > 0:
        k -= (k // l) * l
        t = loop[k]

    print(t)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

takahashi = 1
roop = [takahashi]
roop_flag = False
visited = [False] * N
visited[takahashi - 1] = True

for _ in range(K):
    takahashi = A[takahashi - 1]
    if visited[takahashi - 1]:
        roop_flag = True
        break
    else:
        roop.append(takahashi)
        visited[takahashi - 1] = True

if roop_flag:
    first, roop = roop[:roop.index(takahashi)], roop[roop.index(takahashi):]
    print(roop[(K - len(first)) % len(roop)])
else:
    print(roop[-1])

Submission status: Accepted

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):])
if len(l) > k:
    print(l[k])
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])

Submission status: Accepted

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
else:
    loc = 0
    while k > 0:
        loc = a[loc]
        k -= 1
print(loc+1)

Submission status: Accepted

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

if K == 1:
    print(A[0])
    exit()

if A[0] == 1:
    print(1)
    exit()

# (cnt, k)
visit_town = [(0, 0)]*N
history = [0]*N

visit_town[0] = (1, 0)
history[0] = 1
visit = -1
for i in range(K):
    next_town = A[history[i]-1]
    if visit_town[next_town-1][0] == 0:
        visit_town[next_town-1] = (1, i + 1)
        history[i+1] = next_town
        continue
    mod_k = (K - visit_town[next_town-1][1]) % (i + 1 - visit_town[next_town-1][1])
    visit = mod_k + visit_town[next_town-1][1]
    break
if visit == -1:
    print(history[K])
else:
    print(history[visit])

Submission status: Accepted

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

already = [False for i in range(N)]
already[0] = True
tel = [0]

while True:
    tmp = A[tel[-1]]
    tel.append(tmp)
    
    if already[tmp]:
        tel.pop()
        break
        
    already[tmp] = True

for i in range(len(tel)):
    if tel[i] == tmp:
        s = i
        break
        
if K - s >= 0:
    ans = (K - s) % (len(tel) - s) 
    print(tel[ans + s] + 1)
else:
    print(tel[K] + 1)

Submission status: Accepted

Solution code:
def main():
    n,k = tuple([int(t)for t in input().split()])

    a = tuple([int(t)-1 for t in input().split()])

    route = []
    se = set([])

    t = -1
    s = -1

    looplen = 0

    pos = 0
    for i in range(n):
        route.append(pos)
        se.add(pos)
        if a[pos] in se:
            t = len(route)
            s = route.index(a[pos])
            looplen = t-s
            break  
        pos = a[pos]

    if t>k:
        print(route[k]+1)
    else:
        pos = s+(k-s)%looplen
        print(route[pos]+1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    print(stack[0])
else:
    stack=[1]
    for i in range(K):
        x=stack.pop()
        stack.append(graph[x])

    print(stack[0])

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    D = [0] * (n+1)
    now = 1
    for i in range(1, k+1):
        tmp = A[now-1]
        if not D[tmp]:
            now = tmp
            D[now] += i
        else:
            pre = D[tmp]
            loop = i - D[tmp]
            print(D.index((k - pre) % loop + pre) if loop > 1 else tmp)
            return
    print(now)
main()

Submission status: Accepted

Solution code:
import numpy as np
n,k = map(int, input().split())
a = input().split()
flag = np.zeros((n))
now = 1
memory = []
for i in range(k):
    if flag[now-1] != 1:
        flag[now-1] = 1
        memory.append(now)
        now = int(a[now-1])        
    else :
        index = memory.index(now)
        num = len(memory) - index
        rest = k - i
        shorten = rest % num
        now = memory[index+shorten]
        break
print(now)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest


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

    loop_list = []
    loop_set = set()
    now = 0

    if k > n:
        for _ in range(k):
            now = a[now] - 1

            if now + 1 in loop_set:
                s_index = loop_list.index(now + 1)
                before_loop = s_index
                loop_list = loop_list[s_index:]
                break
            else:
                loop_list.append(now + 1)
                loop_set.add(now + 1)

        l = len(loop_list)
        k -= before_loop

        # print(loop_list, l, before_loop)
        print(loop_list[k % l - 1])
    else:
        for _ in range(k):
            now = a[now] - 1

        print(now + 1)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 5
3 2 4 1"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 727202214173249351
6 5 2 5 3 2"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
import sys 
sys.setrecursionlimit(10000000)


n,k = iim()
A = iil()
d = {0:True}
l = [0]
def move(num):
    l.append(A[num]-1)
    if d.get(A[num]-1,False):
        return True if A[num]-1 == 0 else False
    else:
        d[A[num]-1] = True
        return move(A[num]-1)

if move(0):
    rep = len(l)-1
    ini = 0
else:
    ini = l.index(l[-1])
    rep = len(l)-ini-1

if k <= ini:
    print(l[k]+1)
else:
    mod = (k-ini)%rep
    if mod == 0:
        mod = rep
#    print(l,mod,rep,ini)
    print(l[ini+mod]+1)

Submission status: Accepted

Solution code:
tem1=input().split()
N = int(tem1[0])
K = int(tem1[1])
tem2 = input().split()
jud = [0 for i in range(len(tem2))]
now =1
circle=0
for i in range(0,K):
    if jud[now-1]==0:
        jud[now-1]=i
        now = int(tem2[now - 1])
    else:
        circle=i-jud[now-1]
        fact=(K-i-1)%circle
        for j in range(0,fact+1):
            now = int(tem2[now - 1])
        break

print(now)

Submission status: Accepted

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

Log= N*[-1]
count = 0
i = 1
restartflag = False


while count < K:
    i = A[i - 1]
    # count
    count += 1
    # 訪れたことのある街でない
    if Log[i-1]==-1:
        Log[i-1] = count # n 回目に訪れた
    else:
    # 訪れたことのある街であるならば
        looplen = count - Log[i-1]
        loopstart = Log[i - 1]
        loopend_city= i 
        restartflag = True
        break

if restartflag:
    count = 0
    remain =(K-loopstart) % looplen
    i = loopend_city
    while count < remain:
        i = A[i-1]
        count += 1

print(i)