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: Runtime Error

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

memo = [1]
setm = set(memo)
cnt = 1
to = 1
while cnt <= k:
    to = a[to-1]
    if to not in setm:
        memo.append(to)
        setm.add(to)
        cnt += 1
    else:
        break
        
idx = memo.index(to)
kidx = ((k - len(memo))%(len(memo)-idx))
if len(memo)>k:
    print(memo[-2])
else:
    print(memo[-1] if kidx==0 else: memo[idx:][kidx])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
if (a[0]==1):
    print(1)
    exit()
ans=chk=0
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
if p==0:
    print(w[k%len(w)])
else:
    print(h[0])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
if (a[0]==1):
    print(1)
    exit()
ans=chk=0
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
if p==0:
    print(w[len(w)%k-1])
else:
    print(h[0])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
ans=chk=0
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
    if i==k-1:
        print(t)
        exit()
mae=max(0,w.index(t)-1)
k-=mae
loop=len(w)-mae-1
print(w[k%loop+mae])

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':

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

    B = set()
    cnt = 0
    ind = 1
    startind = 0
    D = []
    while True:
        if A[ind] not in B:
            B.add(ind)
            D.append(ind)
            cnt += 1
            ind = A[ind]
        else:
            B.add(ind)
            D.append(ind)
            cnt += 1
            startind = A[ind]
            break

    C = set()
    ind = startind
    ANS = []
    while True:
        if A[ind] not in C:
            C.add(ind)
            ind = A[ind]
            ANS.append(ind)
        else:
            C.add(ind)
            ANS.append(A[ind])
            break

    if k > cnt:
        tmp = k - cnt
        tmp = tmp % (len(C))
        print(ANS[tmp-1])
    else:
        print(D[k])

Submission status: Runtime Error

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

id = [-1] * N
x = A2[0]
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A2[x]

c = l - id[x]
if K <= l:
    print(a[K] + 1)
else:
    K -= l
    print(a[id[x] + K % c - 1] + 1)

Submission status: Runtime Error

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

id = [-1] * N
x = A[0]
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

c = l - id[x]
if K <= l:
    print(a[K] + 1)
else:
    K -= l
    print(a[id[x] + K % c - 1] + 1)

Submission status: Runtime Error

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

id = [-1] * N
x = A[0]
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

c = l - id[x]
if K <= l:
    print(a[K] + 1)
else:
    print(a[id[x] + K % c - 1] + 1)

Submission status: Runtime Error

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

id = [-1] * N
x = A[0]
l = 0
a = []
for i in range(N):
    if id[x] != -1:
        break
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

if K <= l:
    print(a[K] + 1)
else:
    print(a[K % (l - id[x]) - 1] + 1)

Submission status: Runtime Error

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

id = [-1] * N
x = A[0]
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

if K <= l:
    print(a[K] + 1)
else:
    print(a[K % (l - id[x]) - 1] + 1)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dic={}
wk=1
start=0
for i in range(1,n+1):
  wk=a[wk-1]
  if wk in dic:
    start=dic[wk]
    break
  dic[wk]=i
end=len(dic)
loopcnt=end-start+1
keys=list(dic.keys())
if k<start:
  print(keys[k-1])
else:
  chk=(k-start+1)%loopcntac
  if chk==0:
    chk=loopcnt
  print(keys[(start-1)+chk-1])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
graph = [[] for _ in range(n+1)]
routes= list(map(int, input().split()))
seen = [False] * (n+1)
search_num = [0] * (n+1)
final = 0

for z, point in enumerate(routes):
    graph[z+1].append(point)
    
def dfs(g, point, num=1):
        global final
        seen[point] = True
        search_num[point] = num
        num +=1
        for j in g[point]:
            if seen[j]:
                final = j
                continue
            dfs(g,j, num)
            
dfs(graph,1, 1)
remain_count = k - (search_num[final] - 1)  
loop_length = max(search_num) + 1 - search_num[final] 
remain_count %= loop_length 
ans_value = search_num[final] + remain_count
ans = [i for i in range(len(search_num)) if search_num[i] == ans_value][0]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N,K = map(int,input().split())
A = list(map(int,input().split()))
now = 0
position_list = [0]
cnt = 0
before = -1
while cnt <K:
    now = A[now] -1
    cnt += 1
    if now in position_list:
        for i in range(len(position_list)):
            if position_list[i] == now:
                before = i
        break
    else:
        position_list.append(now)
if before == -1:
    print(now+1)
    sys.exit()
num = K %cnt
print(position_list[now + num] +1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

b = []
bb = defaultdict(int)

# n回以内にある都市に戻る
pos = 1
for i in range(len(a)):
    pos = a[pos - 1]
    if pos in bb: #時間がかかる
        break
    bb[pos] = 1
    b.append(pos)

# ループのスタート都市 loop_city1
loop_city1 = pos
# ループの開始位置
loop_start = b.index(loop_city1)
# ループの終了位置
loop_end = len(b) - 1

# 残りの移動回数をループの長さで割るとループの何番目で終わるか分かる
out = (k - loop_start) % (loop_end - loop_start + 1)
if out == 0:
    out = loop_end - loop_start + 1 + 1

# 最終都市
# ループ前の都市数をずらして
print(b[out + loop_start - 1])

Submission status: Runtime Error

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

b = {}

# n回以内にある都市に戻る
pos = 1
for i in range(len(a)):
    pos = a[pos - 1]
    if pos in b: #時間がかかる
        break
    b.append(pos)

# ループのスタート都市 loop_city1
loop_city1 = pos
# ループの開始位置
loop_start = b.index(loop_city1)
# ループの終了位置
loop_end = len(b) - 1

# 残りの移動回数をループの長さで割るとループの何番目で終わるか分かる
out = (k - loop_start) % (loop_end - loop_start + 1)
if out == 0:
    out = loop_end - loop_start + 1

# 最終都市
# ループ前の都市数をずらして
print(b[out + loop_start - 1])

Submission status: Runtime Error

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

for i in range(N):
    next = A[next - 1]
    root.append(next)

    if len(set(root)) < i + 1:
        roop_start = root.index(next)
        roop_end = i
        roop_cycle = roop_end - roop_start
        root = root[roop_start - 1:roop_end]
        break

if K < roop_cycle:
    print(root[K])
else:
    a = (K - roop_start) % roop_cycle
    if a == 0:
        print(root[roop_cycle])
    else:
        print(root[a - 1])

Submission status: Runtime Error

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

for i in range(N):
    next = A[next - 1]
    root.append(next)

    if len(set(root)) < i + 1:
        roop_start = root.index(next)
        roop_end = i
        roop_cycle = roop_end - roop_start
        root = root[roop_start - 1:roop_end]
        break

if K < roop_cycle:
    print(root[K])
else:
    a = (K - roop_start) % roop_cycle
    if a == 0:
        print(root[roop_cycle])
    else:
        print(root[a - 1])

Submission status: Runtime Error

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

for i in range(N):
    next = A[next - 1]
    root.append(next)

    if len(set(root)) < i + 1:
        roop_start = root.index(next)
        roop_end = i
        roop_cycle = roop_end - roop_start
        root = root[roop_start - 1:roop_end]
        break

if K < roop_cycle:
    print(root[K])
else:
    a = (K - roop_start) % roop_cycle
    print(a)
    if a == 0:
        print(root[roop_cycle])
    else:
        print(root[a - 1])

Submission status: Runtime Error

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

for i in range(1, K + 1):
    next = A[next - 1]
    root.append(next)

    if len(set(root)) < i:
        roop_start = root.index(next)
        roop_end = i
        roop_cycle = roop_end - roop_start
        break

ans_index = (K - roop_start - 1) % roop_cycle
if ans_index == 0:
    if roop_start == 1:
        ans_index = roop_cycle - 1
    else:
        ans_index = roop_start + roop_cycle - 1
else:
    ans_index += roop_start - 1 - 1

print(root[ans_index])

Submission status: Runtime Error

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

dic = {}
for i, v in enumerate(A):
    dic[i+1] = v

town = 1
s = set()
l = []
for _ in range(K):
    l.append(town)
    s.add(town)
    town = dic[town]
    if town in s:
        stop_twon = town
        break

list_first_split = l[:l.index(stop_twon)]
list_second_split = l[l.index(stop_twon):]
print(list_second_split[(K - (len(list_first_split))) % len(list_second_split)])

Submission status: Runtime Error

Solution code:

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
root = [1]
next = 1

for i in range(1, K + 1):
    next = A[next - 1]
    root.append(next)

    if len(set(root)) < i:
        roop_start = root.index(next)
        roop_end = i
        roop_cycle = roop_end - roop_start
        break

ans_index = (K - roop_start - 1) % roop_cycle
if ans_index == 0:
    ans_index = roop_cycle - 1
else:
    ans_index += roop_start - 1 - 1

print(root[ans_index])

Submission status: Runtime Error

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

c = []

# ループする都市を探索
for i in range(len(a)):
    # 自分自身を指していない and 他都市から移動あり
    if a[i] - 1 != i and (i + 1) in a:
        c.append(a[i])
#print(a)

# ループする都市のリスト
c = list(set(c))
#print(c)

# ループする都市をループしたかのチェックフラグ
d = [0] * len(c)

# ループ順のリストの箱
e = []

# ループしだすまでの移動を確認
flag = 0
pos = 1
for i in range(n*2):
    pos = a[pos - 1]
    if pos in c:
        # ループする都市のリストに入った処理
        flag = 1
        for j in range(len(c)):
            if c[j] == pos:
                d[j] = 1
                e.append(pos)
        if sum(d) == len(d):
            # 1ループしたら抜け出し
            #print("loop", i)
            break
    else:
        # ループしない都市での処理
        # 1度ループしだしたら抜けることないのでここは不要？
        flag = 0
        d = [0] * len(c)
        e = []
    #print(pos)

# ループに入るまでの移動を除いて、ループの何番目で終了したかを算出
last_pos = (k - (i - len(c) + 1)) % len(c)
#print(e, i, last_pos)
# ループ順リストから答えを出力
print(e[last_pos - 1])

Submission status: Runtime Error

Solution code:
N,K = map(int, input().split())
A = [int(i) for i in input().split()]
used = [0]
now_town = 0
flag = False

for i,_ in enumerate(range(K)):
    now_town = A[now_town]-1
    if now_town in used:
        break        
    used.append(now_town)
else:
    flag = True

roop_first = used.index(now_town)
ans_index = (K-roop_first)%(i-roop_first+1)

print(now_town+1 if flag else used[roop_first:][ans_index]+1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    n, k = map(int, input().split(" "))
    a = list(map(int, input().split(" ")))
    s = []
    ord = [-1]*(n)
    u = 1
    while ord[u] == -1:
        ord[u] = len(s)
        s.append(u)
        u = a[u-1]
    l = len(s) - ord[u]
    if k < ord[u]:
        print(s[k])
    else:
        print(s[(k-ord[u])%l+ord[u]])

'''
def main():
    n, k = map(int, input().split(" "))
    a = list(map(lambda i: int(i)-1, input().split(" ")))
    s = [0]
    d = defaultdict(lambda:0)
    x = a[0]
    for i in range(n):
        s.append(x)
        x = a[x]

    bb=None
    for i in range(n):
        d[s[i]] += 1
        if d[s[i]] ==2:
            bb=s[i]
            break

    cc = s.index(bb)
    s[cc]=-1
    dd = s.index(bb)
    loop_len = dd-cc
    s[cc]=s[dd]
        
    if bb ==None or k < cc:
        print(s[k]+1)
    else:
        y = (k-cc) % loop_len
        print(s[y+cc]+1)
'''
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def main():
    n, k = map(int, input().split(" "))
    a = list(map(lambda i: int(i)-1, input().split(" ")))
    s = [0]
    u = [0]
    f = True
    loop_len = 1
    z = 0
    x = a[0]
    while f:
        if x in s:
            f = False
            b=s.index(x)
            s = s[b:]
            loop_len = len(s) - b
            z = s.index(x)
        else:
            s.append(x)
            x = a[x]
    y = (k-z) % loop_len
    print(s)
    print(s[y]+1)

    



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
list = []
replist = []
judge = [True] * (2 * 10 ** 5)
cnt = 1
pos = 1
owari = True
while cnt < 2 * 10 ** 5 and owari:
    judge[pos] = False
    list.append(pos)
    pos = A[pos]
    if not judge[pos]:
        while True:
            replist.append(pos)
            judge[pos] = True
            pos = A[pos]
            if judge[pos]:
                owari = False
                break
if K <= len(list)-1:
    print(list[K])
else:
    K = K - len(list) + 1
    print(replist[( K % len(replist) ) -1])

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
b=[False]*n
pos=0
for i in range(k):
    if b[pos]!=False:
        loop=i-b[pos]+1
        break
    b[pos]=i+1
    pos=a[pos]-1
    k-=1

for i in range(k%loop):
    pos=a[pos]-1
print(pos+1)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a_m = max(a)
tt = [-1] * a_m
tt[0] = 0
ans_l = []

i = 0
while True:
    if tt[a[i]-1] != -1:
        loop = i - tt[a[i]-1]
        k -= tt[a[i]-1]
        break
    tt[a[i]-1] = i + 1
    ans_l.append(a[i])
    i += 1

ans_c = k % loop
print(ans_l[ans_c+tt[a[i]-1]])

Submission status: Runtime Error

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

ll = [a[0]]

for i in range(1, n):
    cnt = ll[i-1]
    if cnt = a[cnt-1]:
        print(cnt)
        exit()
    if a[cnt-1] == a[0]:
        break
    else:
        ll.append(a[cnt-1])

print(ll[k%3-1])

Submission status: Runtime Error

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

ll = [a[0]]

for i in range(1, n):
    cnt = ll[i-1]
    if a[cnt-1] == a[0]:
        break
    else:
        ll.append(a[cnt-1])

print(ll[k%3-1])

Submission status: Runtime Error

Solution code:
def dfs(v):
    path.append(v)
    visited[v] = 1
    nv = A[v]
    if visited[nv] == 1:
        return nv
    return dfs(nv)


N, K = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
visited = [-1] * N
path = []
cycle_start = dfs(0)
cycle_len = len(path) - path.index(cycle_start)
head_len = len(path) - cycle_len
if K <= head_len:
    print(path[K] + 1)
else:
    K -= head_len
    print(path[head_len + K % cycle_len] + 1)

Submission status: Runtime Error

Solution code:
from copy import deepcopy

def main():
    n, k = map(int, input().split())
    a = [int(x)-1 for x in input().split()]
    cnt = 0
    next_posi = 0
    # 何回できたことのあるところにいくか
    visited = set()
    visited.add(0)
    for _ in range(n):
        next_posi = a[next_posi]
        cnt += 1
        if next_posi not in visited:
            visited.add(next_posi)
        else:
            break
    # print('cnt', cnt)
    cnt2 = 0
    visited_posi = deepcopy(next_posi)
    for _ in range(k-cnt):
        next_posi = a[next_posi]
        cnt2 += 1
        if next_posi == visited_posi:
            break
    # print('cnt2', cnt2)
    mod = (k-cnt) % cnt2
    # print('mod', mod)
    for _ in range(mod):
        next_posi = a[next_posi]
    print(next_posi+1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
rec = [0]
i = 0
flag = [0 for _ in range(n + 1)]
while True:
    if flag[rec[i]] == 0:
        flag[rec[i]] = 1
        rec.append(a[rec[i]] - 1)
    else:
        start = rec.index(a[rec[i]] - 1)
        loop = rec[start:]
        pre = rec[:start]
        break
    i += 1
count = (k - len(pre)) % len(loop)
if k < len(pre):
    print(loop[k])
else:
    print(loop[count] + 1)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
rec = [0]
i = 0
flag = [0 for _ in range(n + 1)]
while True:
    if flag[rec[i]] == 0:
        flag[a[i]] = 1
        rec.append(a[rec[i]] - 1)
    else:
        start = rec.index(a[rec[i]] - 1)
        loop = rec[start:]
        pre = rec[:start]
        break
    i += 1
count = (k - len(pre)) % len(loop)
print(loop[count] + 1)

Submission status: Runtime Error

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

now = 1
path = [1]

for i in range(N + 2):
    now = A[now]
    path.append(now)

if i >= K:
    print(path[K])
    quit()

now = path.pop()
lo_start = i - 1
while path[lo_start] != now:
    lo_start -= 1

lo_len = i - lo_start
loop = path[lo_start:]

ans = loop[(K - path.index(lo_start)) % lo_len]

print(ans)

Submission status: Runtime Error

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

cnts = [None] * N

pos = 0
cnt = 0

while cnt < K:
    print(cnts)
    if cnts[pos] != None:
        loop_size = cnt - cnts[pos]
        cnt += ((K-cnt) // loop_size - 1) * loop_size
        cnts = [None] * N
    cnts[pos] = cnt
    pos = A[pos]
    cnt += 1

print(pos+1)

Submission status: Runtime Error

Solution code:
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
check = [0]*N
ima = 0
for i in range(K):
  if check[A[ima]-1] != 0:
    loopen = ima
    check[ima] = i+1
    looplen = check[ima] - check[A[ima]-1] + 1
    loopend = i
    break
  check[ima] = i+1
  ima = A[ima]-1
offset = (K-(i-looplen)-1)%looplen
ima = 0
for i in range(loopend-looplen+offset+1):
  ima = A[ima]-1
print(ima+1)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    s_time =time.time()
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
visit = [False for i in range(n)]
loop = 0
now = 1
visit[0] = True
while True:
  now = a[now - 1]
  loop += 1
  if visit[now-1]:
    break
  visit[now-1] = True
p = 1


leng = 0
while True:
  p = a[p - 1]
  leng += 1
  if p == now:
    break 
cnt = (k-leng)%(loop-leng) + leng
  
now = 1
for i in range(cnt):
  now = a[now-1]
print(now)

Submission status: Runtime Error

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

i = 1
pas = [i]
k = K
while k > 0:
    if A[i] in pas:
        break
    pas.append(A[i])
    i = A[i]
    k -= 1

roopindx = pas.index(A[i])

roopi = K%(len(pas)-roopindx)

print(pas[roopi])

Submission status: Runtime Error

Solution code:
def delete_head_zeros(n):
	n = str(n)
	l = len(n)
	if "." in n:
		l = n.find(".")
	head_zeros = 0
	for i in range(l - 1):
		if n[i] == "0":
			head_zeros += 1
		else:
			break

	return n[head_zeros:]

# compare a, b
# a, b: int or string
def bigint_compare(a, b):
	a = delete_head_zeros(a)
	b = delete_head_zeros(b)
	if len(a) > len(b):
		return 1
	elif len(a) < len(b):
		return -1
	else:
		if a > b:
			return 1
		elif a < b:
			return -1
		else:
			return 0

# calculate a + b
# a, b: int or string
def bigint_plus(a, b):
	a = str(a)
	b = str(b)

	d = max([len(a), len(b)])
	a = '0' * (d - len(a)) + a
	b = '0' * (d - len(b)) + b

	ans = ""
	carry = 0
	for i in range(d):
		s = int(a[-i-1]) + int(b[-i-1]) + carry
		carry = s // 10
		ans = str(s % 10) + ans
	else:
		if carry:
			ans = str(carry) + ans

	return ans

# calculate a - b
# a, b: int or string
def bigint_minus(a, b): 
	a = str(a)
	b = str(b)
	M = []
	m = []
	sign = ""

	if len(a) > len(b) or (len(a) == len(b) and a >= b):
		[M, m] = [a, b]
	else:
		[M, m] = [b, a]
		sign = "-"
	m = '0' * (len(M) - len(m)) + m

	ans = ""
	borrow = 0
	for i in range(len(M)):
		s = int(M[-i-1]) - int(m[-i-1]) - borrow
		if s < 0:
			borrow = 1
			s += 10
		else:
			borrow = 0
		ans = str(s) + ans

	return sign + delete_head_zeros(ans)

# calculate a * b
# a, b: int or string
def bigint_multiply(a, b):
	a = str(a)
	b = str(b)

	md = []
	for j in range(len(b)):
		carry = 0
		mj = ""
		for i in range(len(a)):
			m = int(a[-i-1]) * int(b[-j-1]) + carry
			carry = m // 10
			mj = str(m % 10) + mj
		else:
			if carry:
				mj = str(carry) + mj
		md.append(mj)

	ans = 0
	for k in range(len(md)):
		ans = bigint_plus(md[k] + "0" * k, ans)

	return ans


# calculate a / b to d digits after decimal point
# a, b, d: int or string
def bigint_divide(a, b, d = 0):
	a = str(a)
	b = str(b)
	d = int(d)
	if d < 0:
		d = 0

	ans = ""
	r = ""
	for i in range(len(a) + d):
		q = 0
		if i < len(a):
			r += a[i]
		elif i == len(a):
			ans += "."
			r += "0"
		else:
			r += "0"

		if bigint_compare(r, b) == -1:
			ans += str(q)
		else:
			while bigint_compare(r, b) >= 0:
				r = bigint_minus(r, b)
				q += 1
			ans += str(q)

	return delete_head_zeros(ans)

def main():
	N, K = input().split(" ")
	A = [int(a) - 1 for a in input().split(" ")]
	visited = [0] * int(N)
	towns = []
	now = 0
	while visited[now] == 0:
		towns.append(now)
		visited[now] = 1
		now = A[now]
	else:
		loop_begin_idx = towns.index(now)
		loop_end_idx = len(towns) - 1
		loop_n = loop_end_idx - loop_begin_idx + 1
	if int(K) <= len(towns) + 1:
		print(towns[int(K)] + 1)
		return 0
	K_from_loop = bigint_minus(K, loop_begin_idx)
	q = bigint_divide(K_from_loop, loop_n)
	r = bigint_minus(K_from_loop, bigint_multiply(loop_n, q))
	print(towns[loop_begin_idx + int(r)] + 1)

main()

Submission status: Runtime Error

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

visited = [0 for _ in range(N)]
first_visit = [0 for _ in range(N)]

now = 0
flag = True
for i in range(10 ** 5 * 3):
    if first_visit[now] == 0:
        first_visit[now] = i

    visited[A[now] - 1] += 1
    now = A[now] - 1

    if i == K - 1:
        print(now + 1)
        flag = False
        break

if flag:
    num = 0
    for i in range(N):
        if visited[i] > 3:
            num += 1

    for i in range(N):
        if K % num == first_visit[i] % num:
            print(i + 1)

Submission status: Runtime Error

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

v = [-1] * (N + 1)
n = 1
f = 0

for i in range(N):
    v[n] = i
    n = A[n]
    if v[n] != -1:
        f = 1
        s = n #ループのスタート
        t = i
        l = t - v[s] + 1
        break

if t >= K:
    print(v.index(K))
else:
    K = (K - s) % l
    print(v.index(K + s))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[1]
C=["#"]*N
for i in range(K):
    if C[B[i]-1]=="#":
        C[B[i]-1]="$"
    else:
        break
    B.append(A[B[i]-1])

f=B.index(B[i])
T=i-f
r=(K-f)%T
print(B[f+r])

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

flag = 0
done = [0] * (N + 1)

root = []
ind = 0

ind = A[0]
root = [1]
done[1] = 1

while True:

    if done[ind]:
        flag = 1
        break
    done[ind] = 1

    root += [ind]
    ind = A[ind-1]

if flag:
    if len(root) < K:
        left = root.index(ind) - 1
        loopcnt = len(root) - (root.index(ind))

        root2 = root[left+1:]
        print(root2[(K-(left+1)) % loopcnt])
    else:
        print(root[K])
else:
    print(root[K-1])

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

flag = 0
done = [0] * (N + 1)

root = []
ind = 0

ind = A[0]
root = [1]
done[1] = 1

while True:

    if done[ind]:
        flag = 1
        break
    done[ind] = 1

    root += [ind]
    ind = A[ind-1]

if flag:
    if len(root) < K:
        left = root.index(ind) - 1
        loopcnt = len(root) - (root.index(ind))

        root2 = root[left+1:]
        print(root2[(K-(left+1)) % loopcnt])
    else:
        print(root[K])
else:
    print(root[K])

Submission status: Runtime Error

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

from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]

flag = 0
done = [0] * (N + 1)

root = []
ind = 0

ind = A[0]
root = [1]
done[1] = 1

while True:

    if done[ind]:
        flag = 1
        break
    done[ind] = 1

    root += [ind]
    ind = A[ind-1]

print("rootlen : ", len(root))
print("flag : ", flag)

if flag:
    if len(root) < K:
        left = root.index(ind) - 1
        loopcnt = len(root) - (root.index(ind))

        root2 = root[left+1:]
        print(root2[(K-(left+1)) % loopcnt])
    else:
        print(root[K])
else:
    print(root[K])

Submission status: Runtime Error

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

m = [1]
for i in range(k):
  m.append(a[m[i]-1])
  if a[m[i]-1] in m[:i]:
    c = m.index(a[m[i]-1])
    d = i+1 - m.index(a[m[i]-1])
    l = m[c:c+d]
    break

r = (k-c) % d
num = l[r]

if k < d:
  print(m[k])
else:
  print(num)

Submission status: Runtime Error

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

m = [1]
for i in range(k):
  m.append(a[m[i]-1])
  if a[m[i]-1] in m[:i]:
    c = m.index(a[m[i]-1])
    d = i+1 - m.index(a[m[i]-1])
    l = m[c:c+d]
    break

r = (k-c) % d
num = l[r]
print(num)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

visited=[True]*N
visitednum=[]
now=0
for i in range(K+1):
    if not visited[now]:
        break
    else:
        visited[now]=False
        visitednum.append(now)
        now=A[now]
d=visitednum.index(now)
ans=(K-d)%(len(visitednum)-d)+d
print(visitednum[ans]+1)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

visited=[True]*N
visitednum=[]
now=0
for i in range(K):
    if not visited[now]:
        break
    else:
        visited[now]=False
        visitednum.append(now)
        now=A[now]
d=visitednum.index(now)
ans=(K-d)%(len(visitednum)-d)+d
print(visitednum[ans]+1)

Submission status: Runtime Error

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

li = [1]
for i in range(n*2):
    li.append(L[li[-1]-1])
#print(li)

la = li[n]
fi = li[n-1]
i = n
cnt = 0
s = set()
s.add(la)
while la != fi:
    la = li[n]
    fi = li[i-1]
    s.add(fi)
    cnt +=1
    i -=1

j = 0
while True:
    if li[j] in s:
        break
    j +=1

a = (k-j)%cnt

print(li[a+j])

Submission status: Runtime Error

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

li = [1]
for i in range(n):
    li.append(L[li[-1]-1])
#print(li)

la = li[n]
fi = li[n-1]
i = n
cnt = 0
s = set()
s.add(la)
while la != fi:
    la = li[n]
    fi = li[i-1]
    s.add(fi)
    cnt +=1
    i -=1

j = 0
while True:
    if li[j] in s:
        break
    j +=1

a = (k-j)%cnt

print(li[a+j])

Submission status: Runtime Error

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

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

    visited = [False] * N
    visited[0] = True

    index = 0
    visited_index = [0]

    while K:
        index = A[index]
        if visited[index]:
            K -= 1
            start = A.index(A[index])
            loop_index = visited_index[start:]
            print(visited_index[K % len(loop_index)] + 1)
            exit()
        visited_index.append(index)
        visited[index] = True
        K -= 1
    print(index + 1)
    
main()