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: Time Limit Exceeded

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


input = sys.stdin.readline
def IS(cb): return cb(input().strip())
def IL(cb): return [cb(s) for s in input().strip().split()]
def IR(cb, rows): return [IS(cb) for _ in range(rows)]
def ILL(cb, rows): return [IL(cb) for _ in range(rows)]


def solve():
    N, K = IL(int)
    A = IL(lambda x: int(x) - 1)
    memo = [0]
    i = 0
    while(not A[i] in memo):
        memo.append(A[i])
        i = A[i]
    j = 0
    if K < len(memo):
        print(memo[K] + 1)
    else:
        loop = memo[memo.index(A[i]):]
        print(loop[(K - (len(memo) - len(loop))) % len(loop)] + 1)


solve()

Submission status: Time Limit Exceeded

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

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

visited = [0]
now = 1
step = 0
for i in range(k):
    now = a[now-1]
    step += 1
    if now not in visited:
        visited.append(now)
    else:
        ind = visited.index(now)
        loop = visited[ind:]
        tmp = (k-step) % len(loop)
        now = loop[tmp]
        break

print(now)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
dest = [int(x) for x in input().split()]
route = [1]
t = 1
while True:
  if dest[t-1] not in route:
    route.append(dest[t-1])
    t = dest[t-1]
  else:
    loop = route.index(dest[t-1])
    L_loop = len(route) - loop
    break
ans = 0
if K < len(route):
  ans = route[K]
else:
  K = K - len(route)
  ans = route[loop + (K % L_loop)]
print(ans)

Submission status: Time Limit Exceeded

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

pos = 0
cnt = 0
while pos not in history and cnt < k:
  history.append(pos)
  pos = a[pos] - 1
  cnt += 1

if cnt == k:
  print(pos + 1)
else:
  cnt_before = history.index(pos)
  print(history[cnt_before + (k - cnt_before) % (cnt - cnt_before)] + 1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  ls = deque([1])
  loop = []
  tmp = 1
  for i in range(K):
    tmp = A[tmp-1]
    if tmp in ls:
      ls = list(ls)
      loop = ls[ls.index(tmp):]
      break
    ls.append(tmp)
  if K > len(ls):
    print(loop[(K-len(ls)+len(loop))%len(loop)])
  else:
    print(ls[K])
    
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
l = [0] * (n+1)
curr = 0
u = 0
for i in range(k):
    curr = a[curr] - 1
    l[curr+1] += 1
    u += 1
    if max(l) == 3:
        start = l.index(max(l))
        break
if max(l) < 3:
    print(curr + 1)
else:
    curr = start - 1
    l = 0
    while True:
        curr = a[curr] - 1
        l += 1
        if curr + 1 == start:
            break
    k -= u
    k = k%l
    for i in range(k + 10 * l):
        curr = a[curr] - 1
    print(curr + 1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    (N, K) = list(map(int, input().split(' ')))

    A = [0]
    A = A + list(map(int, input().split(' ')))

    a = 1
    b = A[a]
    interval = 0
    for i in range(K):
        a = b
        b = A[a]
        interval += 1
        if a == 1:
            break

    for i in range(K % interval):
        b = A[a]
        a = b
    print(a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
town=input().split()
def teleport(a,b):
  dest=1
  for i in range(a):
    dest=b[int(dest)-1]
    
  return dest
    
print(teleport(K,town))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = lambda: sys.stdin.readline()


def cin_int_list():
    return [int(x) for x in input().split()]


def cin_int_iter():
    return (int(x) for x in input().split())


def cin_int():
    return int(input())


def cout_int_iter(a):
    print(' '.join(map(str, a)))


def iota(n, start=0):
    return list(range(start, n))


def cin_digits_list():
    return [ord(x) - ord('0') for x in input()]


def main():
    n, k = cin_int_iter()

    g = {}

    cycle_starts = None
    for u, x in enumerate(cin_int_list()):
        v = x - 1
        g[u] = v
        if v in g:
            cycle_starts = v

    if cycle_starts:
        cycle_len = 0

        u = cycle_starts
        cycle = []
        while True:
            cycle.append(u)
            u = g[u]

            if u == cycle_starts:
                break

        before_cycle = []
        u = 0

        while u != cycle_starts:
            before_cycle.append(u)
            u = g[u]

        if k < len(before_cycle):
            print(before_cycle[k] + 1)
            return

        if before_cycle:
            k -= len(before_cycle)

        print(cycle[k % len(cycle)] + 1)
        return

    u = 0
    while k:
        u = g[u]
        k -= 1

    print(u + 1)




main()


"""
6 1
6 5 2 5 3 2

6 2
6 5 2 5 3 2

6 3
6 5 2 5 3 2

6 4
6 5 2 5 3 2

6 6
6 5 2 5 3 2

6 5
6 5 2 5 3 2
"""

Submission status: Time Limit Exceeded

Solution code:
def calc(i, k):
    ans_list = [i]
    count = 1
    i = a[i]
    while (i not in ans_list) & (count < n):
        ans_list.append(i)
        count += 1
        i = a[i]
    index = ans_list.index(i)
    ans_list.append(i)
    return count, ans_list

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

count, ans_list = calc(0, k)
if count < k:
    index = ans_list.index(ans_list[-1])
    k = k - index
    ans_list = ans_list[index + 1:]
    print(ans_list[k % len(ans_list) - 1] + 1)
else:
    print(ans_list[k] + 1)

Submission status: Time Limit Exceeded

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

N = NK[0]
K = NK[1]

town = 1
for i in range(K):
  town = A[town-1]
  
print(str(town))

Submission status: Time Limit Exceeded

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

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

res = [0]
tmp = 0

tf = [False for i in range(n)]
tf[0] = True

for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp]:
        start = tmp
        break
    else:
        res = res + [tmp]
        tf[tmp] = True

lenret = len(res)
stridx = res.index(start)

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)

Submission status: Time Limit Exceeded

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

x=1
l=[1]
for i in range(k):
    y=a[x-1]
    if y != 1:
        l.append(y)
        x=y
    else:
        break

mod=k%len(l)
print(l[mod])

Submission status: Time Limit Exceeded

Solution code:
line1 = input().split()
n = int(line1[0])
k = int(line1[1])
a = [int(ai) for ai in input().split()]

route = [0]
for j in range(k):
  now = a[route[j]] - 1
  if now in route:
    break
  else:
    route.append(now)

l_start = route.index(now)
print(route[l_start + ((k - l_start) % (len(route) - l_start))] + 1)

Submission status: Time Limit Exceeded

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

perm = [_ for _ in range(N)]

def powlimit(n):
    y = 1
    cnt = 0
    while y < n:
        cnt += 1
        y *= 2
    return cnt
    
n = powlimit(K)
V = A[:]
p = [0 for _ in range(N)]
v = [0 for _ in range(N)]
while K != 0:
    if K % 2 == 1:
        for _ in range(N):
            p[_] = 0
            p[_] = perm[V[_]-1]
        for _ in range(N):
            perm[_] = p[_]
    for j in range(N):
        v[j] = 0
        v[j] = V[V[j]-1]
    for j in range(N):
        V[j] = v[j]
    K //= 2
print(perm[0]+1)

Submission status: Time Limit Exceeded

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

A    = [int(i)-1 for i in input().split()]

visited_town = []
current_town = 0
loop_flg     = False
visited_town.append(current_town)
for i in range(K):
    current_town = A[current_town]
    if current_town in visited_town:
        visited_town.append(current_town)
        loop_flg = True
        break
    visited_town.append(current_town)


if loop_flg:
    loop_start = visited_town.index(current_town)
    loop_end   = len(visited_town) - 1
    loop_length = loop_end - loop_start
    last_index = (K-loop_start)%loop_length
    current_town = visited_town[loop_start+last_index]

print(current_town+1)

Submission status: Time Limit Exceeded

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

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

    count = 0
    now = 0
    visited = [now+1]
    l = -1
    while count < N:
        if A[now] in visited:
            l = visited.index(A[now])
            break
        else:
            count += 1
            visited.append(A[now])
            now = A[now]-1
    r = len(visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)])
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a=input().split()

l=len(a)

for i in range(0,l):
    a[i]=int(a[i])

p=1
for i in range(0,k):
    p=a[p-1]

print(p)

Submission status: Time Limit Exceeded

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

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

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

print(now)

Submission status: Time Limit Exceeded

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

l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    place = A[place]
    K -= 1
    if place in l:
        count = len(l) - l.index(place)
        print(l[l.index(place) + K%count]+1)
        exit()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
roop_find = [0]
check = [0]
i = 0
count = 0
while a[i]-1 not in roop_find:
    roop_find.append(a[i]-1)
    i = a[i] - 1
    count += 1
b = roop_find.index(a[i]-1)
root = roop_find[b:count+1]

if k < b:
    print(roop_find[k]+1)
else:
    k-=b
    e = k % len(root)
    print(root[e]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
town = [i for i in map(int,input().split())]
i=1
c=0
teleport = [1]
while True:
  tmp = town[i-1]
  c+=1
  if c==k:
    print(tmp)
    exit()
  if tmp in teleport:
    a = teleport.index(tmp)
    b = c-a
    break
  teleport.append(tmp)
  i = tmp
print(teleport[a:][(k-a)%b])

Submission status: Time Limit Exceeded

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

l = []
c = 1
while True:
    c = a[c - 1]
    if len(l) + 1 == k:
        print(c)
        break
    elif c in l:
        i = l.index(c)
        l2 = l[i:]
        print(l2[(k - i) % len(l2) - 1])
        break
    else:
        l.append(c)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
teleport_list = list(map(int, input().split()))
t_cycle = [1]
now = 1
while len(t_cycle) == len(set(t_cycle)):
  now = teleport_list[now-1]
  t_cycle.append(now)

start_cycle = t_cycle[-1]
before_cycle_len = t_cycle.index(start_cycle)
cycle_len = len(t_cycle) - t_cycle.index(start_cycle) - 1

if k <= before_cycle_len:
  print(t_cycle[k])
else:
  print(t_cycle[(k-before_cycle_len)%cycle_len + before_cycle_len])

Submission status: Time Limit Exceeded

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

def main():
    n, k = map(int, input().split())
    nlis = list(map(int, input().split()))

    tmp = 1
    tl = []
    tl_a = tl.append

    if k < n:
        for i in range(k):
            tmp = nlis[tmp - 1]
        print(tmp)
    else:
        for i in range(n):
            if not nlis[tmp - 1] in tl:
                tl_a(nlis[tmp - 1])
                tmp = nlis[tmp - 1]
            else:
                tl = tl[tl.index(nlis[tmp - 1]):]
                print(tl[((k - i) % len(tl)) - 1])
                break

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

c = [None] * 200000
p = 0
st = 0
ed = 0
i = 0
while True:
    c[i] = p
    i += 1
    p = a[p]
    if p in c:
        st = c.index(p)
        ed = i
        break
if k < ed:
    print(c[k] + 1)
else:
    k -= st
    k %= ed - st
    print(c[st + k] + 1)

Submission status: Time Limit Exceeded

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

here = 1
log = [1]
i = K
while i > 0:
    here = A[here-1]

    if here in log:
        loopuntil = log.index(here)
        mod = len(log[loopuntil:])
        i = (K - loopuntil) % mod
        log = []


    else:
        log.append(here)
        i = i - 1

print(here)

Submission status: Time Limit Exceeded

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

A = list(map(int, input().split()))
past = []
now = 1
step = 0
for i in range(K):
    past.append(now)
    now = A[now-1]
    if now in past:
        step += 1
        break

if step > 0:
    id = past.index(now)
    step = len(past) - id
    p = (K-id) % step
    for i in range(p):
        now = A[now-1]

print(now)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
import sys
sys.setrecursionlimit(10**9)

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

    graph = [0] * (N+1)
    for i in range(N+1): #1-indexed
        f = i
        t = A[i-1]
        graph[f] = t


    def solve():
        visited = []
        stack = deque([1])
        x = 1
        count = 0
        while len(stack) > 0:
            x = stack.pop()
            if x in visited:
                break

            visited.append(x)
            stack.append(graph[x])
            count += 1

            if count == K:
                print(stack.pop())
                exit()

        loop_head = x
        head_index = visited.index(loop_head)
        loop_len = len(visited) - head_index

        r = (K-head_index)%loop_len
        print(visited[head_index:][r])


    solve()


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

B = [1]
hop = 0
ans = 0
for n in range(N):
    nc = A[B[n]-1]    
    if nc in B:
        idx = B.index(nc)
        loop = B[idx:]
        break
    B.append(nc)
    K -= 1
    ans = nc
    if K < 1:
        break

if K > 0:
    L = len(loop)
    K = K % L
    K -= 1
    ans = loop[K]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[-1]+A
still=[1]
before=1
rS=-1
root=[1]
while True:
  dest=A[before]
  if dest in still:
    rS=dest
    break
  else:
    still.append(dest)
    root.append(dest)
    before=dest
#print(root,rS)
num=0
for i in root:
  if i==rS:
    break
  num+=1
#print(num)
if K<=num:
  print(root[K])
else:
  K-=num
  root2=root[num:]
  print(root2[K%len(root2)])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split()))
tele = list(map(int, input().split()))
loc = 1
act = [[0]*n for i in range(n)]
count = 1
log = []
log.append(loc)
while True:
  newloc=tele[loc-1]
  log.append(newloc)
  #print(newloc)
  if act[loc-1][newloc-1] == 0:
    act[loc-1][newloc-1] =count
    act[newloc-1][loc-1] =count
  else:
    loop=count-act[loc-1][newloc-1]
    loopstart=act[loc-1][newloc-1]
    break
  count+=1
  loc=newloc

if k <= loopstart:
  ans=log[k]
else:
  num = (k-(loopstart-1)) % loop 
  ans=log[loopstart-1+num]
#print(loop)
#print(loopstart)
#print(count)
#print(act)
#print(log)
print(ans)

Submission status: Time Limit Exceeded

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

perm = [_ for _ in range(N)]

def powlimit(n):
    y = 1
    cnt = 0
    while y < n:
        cnt += 1
        y *= 2
    return cnt
    
n = powlimit(K)
V = [A[:] for _ in range(n)]
for i in range(n-1):
    for j in range(N):
        V[i+1][j] = V[i][V[i][j]-1]
place = 0
while K != 0:
    p = [0 for _ in range(N)]
    if K % 2 == 1:
        for _ in range(N):
            p[_] = perm[V[place][_]-1]
        for _ in range(N):
            perm[_] = p[_]
    K //= 2
    place += 1
print(perm[0]+1)

Submission status: Time Limit Exceeded

Solution code:
t = list(map(int,input().split()))
machi = list(map(int,input().split()))
next = machi[0]
for i in range(1,t[1]):
  next = machi[next-1]
print(next)

Submission status: Time Limit Exceeded

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

location = 0
for i in range(k):
    location = towns[location] - 1

print(location+1)

Submission status: Time Limit Exceeded

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

machi = 1
toutatu = []
while not machi in set(toutatu):
	toutatu.append(machi)
	machi = a[machi-1]
saigo = machi
num = toutatu.index(saigo)
unchi = toutatu[num:]
cnt = len(unchi)
num = toutatu.index(saigo)

if num > k:
	print(toutatu[k])
else:
	print(unchi[(k-num)%cnt])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
li = list(map(int, input().split()))
x = li[0]
for j in range (K - 1):
  x = li[x - 1]

print(x)

Submission status: Time Limit Exceeded

Solution code:
# Code for D - Teleporter
# Use input() to fetch data from STDIN

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

l = [1]
s = 0

while(True):
    i = l[-1] - 1
    n = a[i]
    if n in l:
        s = n
        break

    l.append(n)

si = l.index(s)

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

Submission status: Time Limit Exceeded

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

def main():
    N ,K  =  [int(i) for i in input().split()]
    As =   [int(i) for i in input().split()]

    rireki = []
    loop = ""

    ind = 1
    #a = As[0]
    while(1):
        if ind in rireki:
            loop = ind
            break
        else:
            rireki.append(ind)
            ind = As[ind-1]
    #print(rireki,loop)
    loop_c = len(rireki) - rireki.index(loop)
    if K <= len(rireki)-1:
        print(rireki[K])
    else:
        nokori = K-len(rireki)+1
        ans = nokori % loop_c
        if ans == 0:
            print(rireki[-1])
        else:
            print(rireki[rireki.index(loop)+ans-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [1]
if k > len(list(itertools.permutations(a))):
    for i in range(k % n):
        ans.append(a[ans[i] - 1])
    print(a[-1])
else:
    for i in range(k):
        ans.append(a[ans[i] - 1])
    print(a[-2])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
i = 0
his = []
length = 0

#ループに入ったら偶奇見て処理

if K >= 1000000:
  for j in range(min(2 * N, K)):
    i = A[i]-1
    his.append(i)
    K -= 1
  
#loop or not
  for j in range(0, N):
    for k in range(j+1, j+N-1):
      if his[j] == his[k]:
        length = k-j
        K = K % length
      
while K > 0:
  i = A[i]-1
  K -= 1
    
print(i+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [a-1 for a in A]  # 0-index

    cnt = 0
    i = 0
    appeared = [0]
    roop_s = None
    n_roop = None
    for _ in range(N):
        i = A[i]
        cnt += 1

        if cnt == K:
            return i+1

        # if i == 0:
        if i in appeared:
            for j in range(len(appeared)):
                if appeared[j] == i:
                    roop_s = j
                    n_roop = len(appeared) - roop_s
                    break

            break
        
        appeared.append(i)

    # K > cnt
    rest = (K-roop_s) % n_roop
    i = appeared[roop_s]
    for _ in range(rest):
        i = A[i]

    return i+1


print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]
    L=[1]
    a = A[0]
    while a != 1:
        L.append(a)
        a = A[a-1]
    g = K%len(L)
    print(L[g])
main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
As = list(map(int,input().split()))
mod = 0
route = [0]
pre = 0
i = 0
for k in range(K):
    i = As[i]-1
    if i in route:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
# print(route)
mod = len(route)
print(route[(K-pre)%mod]+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
#n個のまち
#1～n　番号
#テレポーターありゅううううううう
# iの転送先a[i]
# kがすこおおおおおおおおおおおお
# k回テレポートつかうとどのまちいく？

# modるか
# nは2*10**5

machi = 1
toutatu = []
while not machi in toutatu:
	toutatu.append(machi)
	machi = a[machi-1]
saigo = machi
num = toutatu.index(saigo)
unchi = toutatu[num:]
cnt = len(unchi)
num = toutatu.index(saigo)

if num > k:
	print(toutatu[k])
else:
	print(unchi[(k-num)%cnt])

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
town = [int(i) for i in input().split()]
num = 1
for _ in range(k):
    num = town[num-1]
print(num)

Submission status: Time Limit Exceeded

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

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

now = 1

d = []

while True:
    if A[now-1] in d:
        i = d.index(A[now-1])
        check = d[i:]
        break
    d.append(A[now-1])
    now = A[now-1]

    if len(d) >= K:
        break

if K <= len(d):
    print(d[K-1])
else:
    K -= (len(d)-len(check))
    K = K % len(check)
    print(check[K-1])

Submission status: Time Limit Exceeded

Solution code:


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

ne=0
his=[]
l=False
for i in range(min(n,k)):
    if ne in his:
        back=his.index(ne)
        loop=i-back
        l=True
        break
    his.append(ne)
    ne=a[ne]-1
if l:
    ansidx=(k-back)%loop+back
    ans=his[ansidx]+1
else:
    ans=ne+1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

city_No = 0
for i in range(K):
    next_city=A[city_No]
    city_No = next_city-1

print(next_city)

Submission status: Time Limit Exceeded

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

tmp = 1
tl = []

if k < n:
    for i in range(k):
        tmp = nlis[tmp - 1]

    print(tmp)
else:
    for i in range(n):
        if not nlis[tmp - 1] in tl:
            tl.append(nlis[tmp - 1])
            tmp = nlis[tmp - 1]
        else:
            tl = tl[tl.index(nlis[tmp - 1]):]
            print(tl[((k - i) % len(tl)) - 1])
            break

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
s=1
M=[0]
while cnt<n:
    s=A[s-1]
    if s-1 in M:
        imp=s-1
        break
    M.append(s-1)
    cnt+=1
x=M.index(imp)
y=len(M)-x

if k<=x:
    print(M[k]+1)
else:
    N=M[x:]
    print(N[(k-x)%y]+1)

Submission status: Time Limit Exceeded

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

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

print(j)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dfs(num,lis,count,target):
    visited[num]=count
    n_city=A[num]
    if visited[n_city]!=-1:
        lis.append(num)
        if target<=count:
              print(lis[target]+1)
        else:
            rep=len(lis)-visited[n_city]
            target-=visited[n_city]
            amari=target%rep
            temp=lis[visited[n_city]:]
            print(temp[amari]+1)
        exit()
    else:
        dfs(n_city,lis+[num],count+1,target)
    

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

visited=[-1]*N

dfs(0,[],0,K)

Submission status: Time Limit Exceeded

Solution code:
def main():
    (N, K) = list(map(int, input().split(' ')))

    A = [0]
    A = A + list(map(int, input().split(' ')))

    a = 1
    b = A[a]
    for i in range(K):
        a = b
        b = A[a]
    print(a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#167
#d
n,k = map(int, input().split())
ln = list(map(int, input().split()))# まちi にいるとき次に町ln[i-1]へいく
visit = [0]*n 
now= 1
visit[0] =1
before =[1]
while max(visit) <= 1:
    now = ln[now -1]
    before.append(now)
    visit[now-1] += 1
roops = before.index(now)
roop_ln = before[roops:-1]
mae = before[:roops]
if k <len(mae):
    print(mae[k])
elif len(mae) <= k :
    t = k- len(mae)
    print(roop_ln[t%len(roop_ln)])

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
# 循環を調べる
tmp_city=[]
c=0
init_city=0

while (1):
    tmp=a[c]
    if tmp in tmp_city:
        init_city=tmp_city.index(tmp)+1
        tmp_city=[1]+tmp_city
        break
    tmp_city.append(tmp)
    c=tmp-1
if len(tmp_city)>k:
    print(tmp_city[k])
else:
    print(tmp_city[init_city:][(k-(init_city))%len(tmp_city[init_city:])])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict,Counter

sys.setrecursionlimit(10**7)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    n,k=mis()
    a=[0]+lmis()
    memo=[1]
    start=1
    i=0
    while i<k:
        i+=1
        if a[start] not in memo:
            memo.append(a[start])
            start=a[start]
        else:
            memo.append(a[start])
            break
    
    if i==k:
        print(memo[k])
    else:
        rp=[i for i,x in enumerate(memo) if x==memo[-1]]
        roop=rp[1]-rp[0]
        cnt=k-rp[0]
        cnt=cnt-cnt//roop*roop
        print(memo[rp[0]+cnt])




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
L=list(map(int,input().split()))
L.insert(0,0)
#print(L)
prev=L[1]
for i in range(1,k):
	nex = L[prev]
	prev = nex
print(nex)

Submission status: Time Limit Exceeded

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

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

now = 1

d = []

while True:
    if A[now-1] in d:
        i = d.index(A[now-1])
        check = d[i:]
        break
    d.append(A[now-1])
    now = A[now-1]

if K <= len(d):
    print(d[K-1])
else:
    K -= (len(d)-len(check))
    K = K % len(check)
    print(check[K-1])

Submission status: Time Limit Exceeded

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

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

res = [0]
tmp = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tmp in res:
        start = tmp
        break
    else:
        res = res + [tmp]

lenret = len(res)
stridx = res.index(start)

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)

Submission status: Time Limit Exceeded

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

l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    place = A[place]
    K -= 1
    if place in l:
        s = place
        break

l=[]
count = 0
while True:
    l.append(place)
    place = A[place]
    count += 1
    if place == s:
        break
print(l[K%count]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
s=[]
s.append(1)
a1=1
a2 = a[a1-1]

while a2 not in s:
    s.append(a2)
    a1 = a2
    a2 = a[a1-1]

loop_num=s.index(a2)
loop=s[loop_num:]
cnt=len(loop)

if k<len(s):
    print(s[k])
else:
    ans = (k-loop_num)%cnt
    print(loop[ans])

Submission status: Time Limit Exceeded

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

position = 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 exp.count(position) == 0:
      exp.append(position)
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])

Submission status: Time Limit Exceeded

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n, k = input_to_int_map()
    a = input_to_int_tuple()

    place = 1
    place_goned = [place]
    i = 0
    while i < n:
        place = a[place - 1]
        if place in place_goned:
            break

        place_goned.append(place)
        i += 1

    if k < len(place_goned):
        return place_goned[k]

    pre_loop_cnt = place_goned.index(place)
    move_cnt = k - pre_loop_cnt
    loop_list = place_goned[pre_loop_cnt:]
    return loop_list[move_cnt % len(loop_list)]


if __name__ == "__main__":
    print(main())