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:
n,k=map(int,input().split())
a=list(map(int,input().split()))
t=1
s=[1]
m=0
u=0
flag="T"
for i in range(k):
  t=a[t-1]
  if t in s:
    u=s.index(t)
    m=i-u+1
    flag="F"
    break
  if flag=="F":
    break
  s.append(t)
if flag=="F":
  print(s[(k-u)%m+u])
else:
  print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    tree = [[] for _ in range(n)]
    for idx, a in enumerate(A):
        tree[a - 1].append(idx)
        tree[idx].append(a - 1)

    start = []
    depth = [0 for _ in range(n)]

    def dfs(v, p, d):
        depth[v] = d
        for u in tree[v]:
            if u == p:
                continue

            if visited[u]:
                start.append([u + 1, depth[u]])
                return
            else:
                visited[u] = True
                dfs(u, v, d + 1)
        return

    visited = [False for _ in range(n)]
    visited[0] = True
    dfs(0, -1, 0)
    
    for i in range(n):
        if i + 1 not in set(A):
            depth[i] = 0

    if k <= start[0][1]:
        print(depth.index(k) + 1)
    elif len(start) == 1:
        print(start[0][0])
    else:
        cnt = (k - start[0][1]) % (start[-1][1] - start[0][1] + 1)
        res = start[0][1] + cnt
        print(depth.index(res) + 1)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

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

loop_lis = [0]
for i in range(K):
  loop_lis.append(A[loop_lis[-1]])
  if len(loop_lis) != len(set(loop_lis)):
    break
for j in range(len(loop_lis)):
  if loop_lis[j] == loop_lis[-1]:
    break
if i == K-1:
  print(loop_lis[-1]+1)
else:
  print(loop_lis[j+(K-j)%(i+1-j)]+1)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split(" "))
a = list(map(int,input().split(" ")))
memory = [1]
i = 1
for j in range(n):
  if not a[i-1] in memory:
    memory.append(a[i-1])
    i = a[i-1]
  else:
    start = memory.index(a[i-1])
    break
if k < len(memory):
  print(memory[k])
else:
  loop = len(memory)-start
  town = (k - start) % loop
  print(memory[town + start])

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    now=1
    t=0
    res=0
    for t in range(k):
        now=a[now-1]
        
    res=now
    print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import stdin


def main():
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    As = [int(x) for x in stdin.readline().rstrip().split()]
    pos = 1
    tmp = deque([pos])
    for _ in range(K):
        pos = As[pos - 1]
        if pos in tmp:
            idx_s = tmp.index(pos)
            break
        tmp.append(pos)
    else:
        print(list(tmp)[-1])
        return

    K = K - idx_s
    tmp = list(tmp)
    print(tmp[idx_s:][K % (len(tmp) - idx_s)])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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 = []
flag = False
for i in range(k):
    target = g[target]
    if target not in visited:
        visited.append(target)
    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: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
cities = {}
city = 1
for i, j in enumerate(map(int, input().split()),1):
    cities[i] = j
while K:
    city = cities[city]
    K -= 1
print(city)

Submission status: Time Limit Exceeded

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

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

now=1
count=0
newWhere=[]
while count>=0:
  now=where[now-1]
  count=count+1
  newWhere.append(now)
  if(now==1):
    break
k=k%count

print(newWhere[k-1])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
posi = 1
tran = [1]
for i in range(k):
    posi = A[posi-1]
    if posi in tran:
        break
    tran.append(posi)
roop = tran[tran.index(posi):]
div = len(tran) - len(roop)
k -= div
p = len(roop)
q = k%p
#print(roop)
#print(p)
print(roop[q])

Submission status: Time Limit Exceeded

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


Town=1
X=0


for i in range(0,K):
      X=ar[(Town-1)]
      Town=(X)
      
print(Town)

Submission status: Time Limit Exceeded

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

i = 1
j = 0

while j < K:
  i = l[i-1]
  j += 1

print(str(i))

Submission status: Time Limit Exceeded

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

c = list()
i = 1
while True:
    if a[i] in c:
        break
    else:
        c.append(a[i])
        i = a[i]

s = c.index(a[i])

if k < s:
    print(c[k-1])
else:
    k -= s
    c = c[s:]
    ans = c[k % len(c) - 1]
    print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]
lnew = [1]
for i in range(n):
  lnew.append(a[l[i]-1])
  if lnew[-1] in l == True:
    break
  else:
    l.append(lnew[-1])

del l[-1]
lindex = l.index(l[-1])
del l[-1]
r = len(l) - lindex
rlist = l[lindex:]

if k >= lindex:
  kmod = (k - lindex) % r
  ans = rlist[kmod]
else:
  ans = l[k]
  
print(ans)

Submission status: Time Limit Exceeded

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

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 = i+1
stridx = res.index(tmp)

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()))
ans = 1
c = [1]
for j in range(1,2*n):
    i = a[c[-1]-1]
    if i in set(c):
        g = i
        break
    c.append(i)
s = c.index(g)
r = len(c)-s
if k <=s:
    print(c[k])
else:
    b = (k-s)%r
    print(c[s+b])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
stack = [A[1]]
idx_list = [1]
while True:
    last = A[stack[-1]]
    if last in stack:
        ind = stack.index(last)
        if ind == stack[-1]:
            break
    idx_list.append(stack[-1])
    stack.append(last)
    if len(stack) == K:
        print(stack[-1])
        exit(0)
mod = len(stack[ind:])
idx = ind + (K-ind-1)%mod
print(stack[idx])

Submission status: Time Limit Exceeded

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

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

if step > 0:
    id = past.index(now)
    step = i+1 - id
    p = (K-id) % step
    now = past[id+p]

print(now)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
L = list(map(int,input().split()))
ans = L[0]
while k-1 > 0:
    ans = L[ans-1]
    k -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
origin = 1
now = origin
for i in range(1, k+1):
    new = a[now-1]
    now = new
    if now == origin:
        roop = i
        k = k % roop
        now = 1
        for j in range(k):
            new = a[now-1]
            now = new
print(now)

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
    checked_list = [1]
    for i in range(K):
        a = b
        b = A[a]
        if a not in checked_list:
            checked_list.append(a)
        else:
            # print(checked_list, a)
            # print(checked_list.index(a), len(checked_list))
            break

    interval = len(checked_list) - checked_list.index(a)
    for i in range((K-checked_list.index(a)) % 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())
a = list(map(int,input().split()))
l = 0    
for i in range(k) :
   # m = a[l]
    l = a[l]-1 
print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

a = [1]
r = -1
loc = 1


for i in range(N):
	loc = A[loc-1]
	#print(loc)
	if not loc in a:
		a.append(loc)
		#print(a)
	else:
		r = i+1
		loop_start = loc
		break

#print(a)
#print(r)
#print(loop_start)

for i in range(N):
	if a[i] == loop_start:
		l = i
		break

first = a[:l]
loop = a[l:]

#print(l, r)
#print(first)
#print(loop)


K += 1

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

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string,decimal
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N,K = II()
A = LI()
past = []
past.append(0)
now = 0
cnt = 1
for k in range(K):
  now = A[now]-1
  if now in past:
    past = past[past.index(now)::]
    print(past[(K - cnt) % len(past)]+1)
    exit()
  cnt += 1
  past.append(now)
print(now+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [0] + A
stack = [A[1]]
idx_list = [1]
while True:
    last = A[stack[-1]]
    if last in stack:
        ind = stack.index(last)
        if ind == stack[-1]:
            break
    idx_list.append(stack[-1])
    stack.append(last)
    if len(stack) == K:
        print(stack[-1])
        exit(0)
mod = len(stack[ind:])
idx = ind + (K-ind-1)%mod
print(stack[idx])

Submission status: Time Limit Exceeded

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 = []
    now = 0

    if k > n:
        while 1:
            now = a[now] - 1

            if now + 1 in loop_list:
                s_index = loop_list.index(now + 1)
                before_loop = s_index
                loop_list = loop_list[s_index:]
                break
            else:
                loop_list.append(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: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
n,k =map(int,input().split())
A = [int(x)-1  for x in input().split()]
arrive_time = [0]*n
time = 1
done = [A[0]]
arrive_time[A[0]] = time
last = 0
while True:
    v = done[-1]
    if not(A[v] in done):
        done.append(A[v]) 
        time += 1
        arrive_time[A[v]] = time
    else:
        last = A[v]
        break  

if time >= k:
    for i,a in enumerate(arrive_time):
        if a == k:
            print(i+1)
else:
    roop = time - arrive_time[last] + 1
    nokori = (k-arrive_time[last])%roop
    ans = nokori+arrive_time[last]
    for i,a in enumerate(arrive_time):
        if a == ans:
            print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
m = 0
for l in range(k):
    g = a[m] - 1
    m = g
print(m + 1)

Submission status: Time Limit Exceeded

Solution code:
N,K=(int(x) for x in 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()))

visited=[0]*n
if k<=n:
    now=0
    nex=0
    loop_start=0
    target=0

    for i in range(n):
        now=nex
        visited[now]+=1
        nex=a[now]-1
        if i+1==k:
            print(nex+1)
            exit()
now=0
nex=0
loop_start=0
target=0
lis=[]
flag=False

for i in range(2*n):
    now=nex
    visited[now]+=1
    nex=a[now]-1
    if flag:
        if now+1 not in lis:
           lis.append(now+1)
           continue
        else:
            break
    if visited[now]==2:
        loop_start=i
        target=now+1
        lis.append(now+1)
        flag=True


dif=len(lis)
first=loop_start-dif
k-=first
print(lis[k%dif])

Submission status: Time Limit Exceeded

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

N,K=(int(x) for x in input().rstrip('\n').split())
As = [int(x)-1 for x in input().rstrip('\n').split()]
now=0
pas = [0]
for i in range(N):
  now = As[now]
  pas.append(now)
  if now in pas[:-1]:
    arrive = pas.index(now)
    loop = len(pas)-arrive-1
    break
if K<=arrive:
  print(pas[K]+1)
else:
  les = K-arrive
  les = les%loop
  res = arrive+les
  print(pas[res]+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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


print(now+1)

Submission status: Time Limit Exceeded

Solution code:
data = input().rstrip().split(" ")
tele = input().rstrip().split(" ")
telepo = [int(i) for i in tele]

max = int(data[1])
limit = max
times = 0
pos = 1
experience = [1]
while max > 0:
    pos = telepo[pos - 1]
    max -= 1
    times += 1
    #print(pos)
    if pos in experience:
        length = len(experience) - experience.index(pos)
        max = max % length
        if max == 0:
            break
        while max > 0:
            pos = telepo[pos - 1]
            max -= 1
            times += 1
            #print(pos)
        break
    experience.append(pos)
print(pos)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

cl=[]
city=1
count=0
while city not in cl:
    count+=1
    cl.append(city)
    city=a[city-1]
#arrive at city in count, len(cl)=count
if k<count:
    print(cl[k])
    sys.exit()
    
loop=0
for i in range(len(cl)):
    if cl[i]==city:
        loop=len(cl)-i
        break

d=(k-count)%loop

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

print(city)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A_list = tuple((map(int,input().split())))
location = 1
 
for k in range(K):
    location = A_list[location-1]
    
print(location)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,k = map(int,stdin.readline().rstrip().split())
a = list(map(int,stdin.readline().rstrip().split()))
a = [0]+a
bunki = 0
now = a[1]
lip = [1]
while True:
    bunki += 1
    if now in lip:
        break
    lip.append(now)
    now = a[now]

tenki = lip.index(now)

lis = lip[tenki:]

roop = bunki-tenki

if k < tenki: 
    print(lip[k])
    exit()
k -= tenki

print(lis[k%roop])

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    #
    # visited = [-1 for _ in range(N)]
    # visited[0] = 0
    #
    # current = 0
    # th = -1
    # per_loop = -1
    # for i in range(1, N):
    #     current = A[current] - 1
    #
    #     if visited[current] >= 0:
    #         # print(i, current, visited[current])
    #         per_loop = i - visited[current]
    #         th = visited[current]
    #         break
    #     else:
    #         visited[current] = i
    #
    # current = 0
    # # print(th, per_loop)
    # # print(th + (K - th) % per_loop)
    #
    # if th < 0:
    #     num_rep = K
    # else:
    #     num_rep = th + (K - th) % per_loop
    #
    # for i in range(num_rep):
    #     current = A[current] - 1
    #
    # print(current + 1)

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

    print(current + 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():  
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  ls = []
  loop = []
  tmp = 1
  i = 0
  while not tmp in ls:
    if i == K:
      print(tmp)
      exit()
    i += 1 
    ls.append(tmp)
    tmp = A[tmp-1]
  loop = ls[ls.index(tmp):]
  print(loop[(K-len(ls)+len(loop))%len(loop)])
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

for _ in range(K):
	arrival = A[arrival - 1]
  
print(arrival)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections

def solve(N,K,A):
    ans = [1]
    i = 0
    while True:
        if(A[i] in ans):
            if(K <= len(ans)):
                return ans[K]
            else:
                index = ans.index(A[i])
                K -= len(ans[:index])
                ans = ans[index:]
            break
        else:
            ans.append(A[i])
            i = A[i] - 1
    return ans[K % len(ans)]
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    # solve()
    print(solve(N,K,A))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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])
        idx = i
        i = A[i]
    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:
import sys

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

dic = {}
for i in range(1, n+1):
    dic[i] = A[i-1]

L = [1]
tmp = 1
ct = 0
check = 0
while True:
    x = dic[tmp]
    ct += 1
    if x in L or ct > k:
        check = x
        break
    else:
        L.append(x)
        tmp = x
if ct > k:
    print(L[k])
    sys.exit()
p = L.index(check)
l = len(L)
roop = l - p
if k < p:
    print(L[k])
else:
    k -= p
    k %= roop
    print(L[p + k])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,k=mp()
a=lmp()
l=[]
i=0
while a[i] not in l:
    l.append(a[i])
    i=a[i]-1


x=l.index(a[i])
y=len(l)-x

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

Submission status: Time Limit Exceeded

Solution code:
n,k,*a = map(int,open(0).read().split())
a = [i-1 for i in a]
c = [0]
for i in range(n):
  nt = a[c[-1]]
  if nt in c:
    ws = c.index(nt)
    wst = c[:ws]
    wrt = c[ws:]
    wr = len(wrt)
  else:
    c.append(nt)
#print(c,ws,wst,wr,wrt)
if ws > k:
  ans = wst[k]
else:
  ans = wrt[(k-ws)%wr]
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import stdin
  N, K = map(int, input().split())
  route = list(map(int, stdin.readline().split()))
  n_place = 1
  trails = [1]
  flg = 0
  for i in range(K):
    n_place = route[n_place - 1]
    if n_place in trails:
      start = trails.index(n_place)
      kyori = i - trails.index(n_place) + 1
      loop = trails[start : start + kyori]
      flg = 1
      break
    else:
      trails.append(n_place)
    if i == K - 1:
      print(n_place)
  if flg == 1:
    print(loop[(K - start) % kyori])
    
main()

Submission status: Time Limit Exceeded

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

counter = 0
city = 1
tf = 0
list_city = [1]

while tf == 0 and counter < k:
    temp = A[city-1]
    city = temp
    if city in list_city:
        tf = 1
    else:
        list_city.append(temp)
        counter+=1

if tf == 1:
    print(list_city[list_city.index(city)+(k-list_city.index(city))%(counter-list_city.index(city)+1)])
else:
    print(city)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
check = []
now = 0
turn = k
while turn > 0:
    if now in check:
        ind = check.index(now)
        x = (turn%(len(check)-ind))-1
        if x == 0:
            x = len(check)-ind-1
        now = a[check[x+ind]]-1
        break
    else:
        turn -= 1
        check.append(now)
        now = a[now]-1
print(now+1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()

a = [1]
r = -1
loc = 1


for i in range(N):
	loc = A[loc-1]
	#print(loc)
	if not loc in a:
		a.append(loc)
		#print(a)
	else:
		r = i+1
		loop_start = loc
		break

#print(a)
#print(r)
#print(loop_start)

for i in range(N):
	if a[i] == loop_start:
		l = i
		break

first = a[:l]
loop = a[l:]

#print(l, r)
#print(first)
#print(loop)


K += 1

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

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
A = [int(x)-1 for x in input().split()]
past = 0
history = [0]
while True:
    na = A[past]
    if na in history: 
        break
    history.append(na)
    past = na
s = history.index(na)
e = len(history)
loop = e - s
if K <= s: # ループ前終了
    print(history[K]+1)
else:
    k = K - s
    print(history[s+(k%loop)]+1)

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
h=[]
go=0
i=0
while(go==0):
    i+=1
    
    

    h.append(p)
    p=a[p-1]
    if i==k:
        break
    if p in h:
        l=len(h)
        for j in range(0,l):
            if h[j]==p:
                amari=(k-i-1)%(i-j)
                go=1

if go==1:
    for i in range(0,amari+1):
        p=a[p-1]

print(p)

Submission status: Time Limit Exceeded

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

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


from_ = 1
way = []
way.append(1)
for i in range(K):
    if(A[from_ - 1] in way):
        way.append(A[from_ - 1])
        break
    else:
        way.append(A[from_ - 1])
        from_ = A[from_ - 1]

key_from = way.index(way[len(way) - 1])
key_to = len(way) - 1



if(K > key_from):
    ans_loop = (K - key_from) % (key_to - key_from)
    ans_num = key_from + ans_loop
   
    print(way[ans_num])
else:
    print(way[K])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [A[k]-1 for k in range(N)]
now = 0
for k in range(1000):
    if (K>>k)&1 == 1:
        now = A[now]
    A = [A[A[l]] for l in range(N)]
print(now+1)

Submission status: Time Limit Exceeded

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

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

now=1
count=0
while count>=0:
  now=where[now-1]
  count=count+1
  if(now==1):
    break
k=k%count


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 = list(map(int, input().split()))
pos = 1
lst = [1]
for i in range(k):
    pos = a[pos-1] 
    if pos in lst:
        num = lst.index(pos)
        loop = len(lst) - num
        rem = (k - i - 1) % loop
        print(lst[num + rem])
        break
    lst.append(pos)
else:
    print(pos)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split(" "))
a = list(map(int,input().split(" ")))
memory = [1]
i = 1
while True:
  if not a[i-1] in memory:
    memory.append(a[i-1])
    i = a[i-1]
  else:
    start = memory.index(a[i-1])
    break
if k < len(memory):
  print(memory[k])
else:
  loop = len(memory)-start
  town = (k - start) % loop
  print(memory[town + start])

Submission status: Time Limit Exceeded

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

(N, K) = (int(i) for i in input().split())

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

# 一周する数を求める
have_been = [1]
now_place = 1
while True:
    next_place = A[now_place - 1]
    if next_place not in have_been:
        have_been.append(next_place)
        now_place = next_place
    else:
        break

#print('have_been = {}'.format(have_been))
loop_start_index = have_been.index(next_place)

loop = have_been[loop_start_index:]
#print('loop = {}'.format(loop))

left_K = K - loop_start_index
if left_K <= 0:
    print(have_been[K])
    sys.exit()

mod = left_K % len(loop)
print(have_been[mod + loop_start_index])

Submission status: Time Limit Exceeded

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

l = [1]

flag = True

while flag:
    next = list_A[l[-1] - 1]

    if not next in l:
        l.append(next)

    else:
        start = l.index(next)
        roop = len(l) - start
        flag = False

if len(l) == 1:
    print(1)
    exit()

elif len(l) >= K:
    print(l[K])
    exit()

else:
    roop_remainder = (K + 1 - start) % roop
    if roop_remainder == 0:
        print(l[-1])
    else:
        print(l[start + roop_remainder -1])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
city_num, cnt = map(int, input().split())
lst = list(map(int, input().split()))
a = lst[0]
for _ in range(cnt - 1):
    a = lst[a - 1]
print(a)