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: Wrong Answer

Solution code:
(town, tele)=[int(x) for x in input().split()]
pos=[int(x) for x in input().split()]
move=[pos[0]]
while True:
  move.append(pos[move[-1]-1])
  if move.count(move[-1]) == 2:
    break
loop_move=move[move.index(move[-1]):-1]
print(loop_move[(tele-(len(move)-1))%len(loop_move)-1])

Submission status: Wrong Answer

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

my_dict = dict()

ptr = 0
cnt = 0

while True:
    if ptr in my_dict:
        break
    else:
        my_dict[ptr] = cnt
        cnt += 1
        ptr = a_ls[ptr] - 1

loop = cnt - my_dict[ptr]

k = k % loop + loop * (10 ** 6 // loop)

ptr = 0

for i in range(k):
    ptr = a_ls[ptr] - 1

print(ptr + 1)

Submission status: Wrong Answer

Solution code:
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]

N,K = read_int_map()
An = read_int_list()
memo = [0]*(N+1)
memo_indx = [0]*(N+1)
memo[1] = 1
memo_indx[1] = 0
seq_an = [1]
next_place = An[0]
for i in range(len(An)):
    if memo[next_place] == 0:
        seq_an.append(next_place)
        memo[next_place] = 1
        memo_indx[next_place] = i + 1
        next_place = An[next_place-1]
    else:
        break
loop_idx = memo_indx[next_place]
loop_list = seq_an[loop_idx:]
if K <= len(seq_an):
    print(seq_an[K-1])
else:
    num = (K - len(seq_an)) % len(loop_list)
    print(loop_list[num])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [0]+list(map(int,input().split()))
b = [0]*(n+1)
cnt = 0
temp = 1
rep = 0
while 1:
    cnt += 1
    if b[temp] == 0:
        b[temp] = cnt
    else:
        rep = cnt-b[temp]
        # print(rep,cnt-1,b[temp])
        # print(b)
        break
    temp = a[temp]
# print((k-b[temp]+1) % rep)
for i in range((k-b[temp]+1) % rep):
    temp = a[temp]
print(temp)

Submission status: Wrong Answer

Solution code:
import math,sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda:int(input())
li = lambda:list(map(int,input().split()))

def case():
    n,k=li()
    a=li()
    d=defaultdict(int)
    i=0
    d[1]=1
    c=0
    ans=[1]
    while(a[i] not in d):
        d[a[i]]=1
        c+=1 
        ans.append(a[i])
        i=a[i]-1
    #print(ans)
   # print(i)
    for j in range(len(ans)):
        if(ans[j]==a[i]):
            ans=ans[j:]
            k-=j
            break 

    #print(ans,k)
    print(ans[(k)%len(ans)])
    




for _ in range(1):
    case()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

n, k, *a = map(int, sys.stdin.read().split())
for i in range(n):
    a[i] -= 1

def main():
    r = k
    cnt = [None] * n
    cnt[0] = 0
    now = 0
    for i in range(1, n + 1):
        now = a[now]
        if not cnt[now] is None:
            r -= cnt[now]
            loop = i - cnt[now]
            break
        cnt[now] = i
    r %= loop 
    for _ in range(r):
        now = a[now]
    print(now + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

d = defaultdict(lambda: -1)
d[1] = 0
L = [1]
i = 0
k = i
while i<N:
    if d[A[k]]==-1:
        d[A[k]] = i+1
        L.append(A[k])
        k = A[k]-1
    else:
        p = d[A[k]]
        q = i+1
        break
    i += 1

L = L[p:]
print(L[(K-p)%(q-p)])

Submission status: Wrong Answer

Solution code:
s = list(map(int,input().split()))
n=s[0]
k=s[1]
s = list(map(int, input().split()))
ans=1
path=[1]
for i in range(k):
    ans=s[ans-1]
    if ans in path:
        loop = path[path.index(ans):]
        ran=len(loop)
        ansour=(k-i-1)%ran
        print(loop,ansour)
        print(loop[ansour])
        break
    path.append(ans)

Submission status: Wrong Answer

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

x = 0
l = [0]
s = set([0])
flag = False
for i in range(N):
    x = A[x]-1
    if x in s:
        break
    l.append(x)

for i in range(len(l)):
    if l[i]==x:
        break

y = len(l)
z = i

if K<len(l):
    print(l[K]+1)
else:
    #print(z)
    #print(y)
    #print(l)
    #print((K-z)%(y-z))
    #print(z)
    print(l[z-1 + (K-z)%(y-z)]+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))

# A[0]から出発して何回でループするか数える

visited = [0]*n


def dfs(v):
    if visited[v]+1 == 3:
        return 0
    visited[v] += 1
    dfs(A[v])


dfs(0)

c = Counter(visited)
loop_cnt = c[2]
init_cnt = c[1]
k -= init_cnt
k %= loop_cnt

cnt = 0
visited = [0]*n


ans = 0
for _ in range(k+init_cnt):
    ans = A[ans]
print(ans+1)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
def solve(n, k, a):
    seen = set()
    cycle = []
    start = 1
    while start not in seen:
        seen.add(start)
        cycle.append(start)
        start = a[start-1]
    idx = cycle.index(start)
    pre = idx
    cycle_len = len(cycle)- idx
    k = (k+1-idx) % cycle_len
    cycle = cycle[idx:]
    return cycle[k-1]
print(solve(N,K,A))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = [-1 for _ in range(n)]
cnt[0] = 0
next_idx = a[0] - 1

f = False
f_idx = -1
start = 0
cost = 0
for i in range(k):
    i += 1
    if cnt[next_idx] != -1:
        f = True
        f_idx = i - cnt[next_idx]
        cost = i
        start = next_idx
        break
    cnt[next_idx] = i
    next_idx = a[next_idx] - 1

if f:
    for i in range(cost, cost + ((k - cost) % f_idx)):
        next_idx = a[next_idx] - 1
print(next_idx+1)

Submission status: Wrong Answer

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 == 0:
        break
    else:
        res = res + [tmp]

lenret = len(res)

tmp = k % lenret

print(res[tmp]+1)

Submission status: Wrong Answer

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

x=1
c=1
while x not in y:	
	y.append(x)
	x=l[x-1]
	
#	print(y)
	c+=1
c=len(y)-y.index(x)
#print(c)
k=k%c
x=1
#print(c)
for i in range(k): 
	x=l[x-1]
print(x)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N, K = mis()
    A = [a-1 for a in mis()]
    B = [None]*N
    now = 0
    B[now] = 0
    for i in count(1):
        now = A[now]
        K -= 1
        if B[now] is not None:
            K %= (i - B[now])
            break
        B[now] = i
    for _ in range(K):
        now = A[now]
    print(now+1)

main()

Submission status: Wrong Answer

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)
cnt=len(s)-loop_num

ans = k%cnt
print(s[ans])

Submission status: Wrong Answer

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

ans = A[0]
for i in range(a - 1):
  #print(ans)
  ans = A[ans - 1]
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def bfs(graph, initial, MX):
    n = len(graph) - 1
    dist = [-1] * (n + 1)
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True
    dist = []

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]
        dist.append(edge)

        if len(dist) == MX:
            return dist

        for i, e in enumerate(nxt):
            q.append(e)

    return dist


def main():
    N, K = MI()
    A = [i-1 for i in MI()]
    edges = [[] for i in range(N)]
    LIMIT = 3*10**5

    for i in range(N):
        edges[i].append(A[i])

    ret = bfs(edges, 0, LIMIT)
    print(ret[K % LIMIT]+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

tmp = a[0]

visit = []
visit.append(str(0))
visit.append(str(tmp-1))

#print('start', 0)
count = 1
ans_on = 0
#print('tmp', tmp-1)
#print('############################')
for i in range(n+1):
    #print('visited', visit)
    #print('count', count)
    count += 1
    tmp = a[tmp-1]
    #print('tmp', tmp - 1)

    if str(tmp-1) in visit:
        on_index = visit.index(str(tmp-1))
        visit_len = len(visit)
        loop_list = visit[on_index:]

        k_ = k-count
        k_tmp =  k_ % (visit_len-on_index)

        ans = loop_list[k_tmp]
        ans_on = 1
        #print('########################')
        break

    visit.append(str(tmp-1))

    #print('########################')

if ans_on == 0:
    #print('last not loop', tmp+1)
    print(tmp+1)
else:
    #print('last', int(ans)+1)
    print(int(ans)+1)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, k = map(int, input().split())    
a = [i - 1 for i in list(map(int, input().split()))]
# print(a)
b = []
current = 0
# cnt = 0
visited = [0 for i in range(n)]
# print("a =", a)
while True:
    if visited[current] == 1:
        break 
    visited[current] = 1
    b.append(current)
    current = a[current]
# print("b =", b)
m = len(b)
ans = b[k % m] + 1
print(ans)

Submission status: Wrong Answer

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

tlist=[]
pos=1
pos_set=set()
while True:
  tlist.append(pos)
  if pos in pos_set:
    break
  pos_set.add(pos)
  pos=alist[pos]
  
dup_pos2=len(tlist)-1
dup_pos1=-1
for i in range(len(tlist)):
  if tlist[i]==tlist[-1]:
    dup_pos1=i
    break
    
print(tlist)
cycle=dup_pos2-dup_pos1
#print(dup_pos1,dup_pos2,cycle)
if K<len(tlist):
  print(tlist[K])
else:
  print(tlist[(K-dup_pos1)%cycle+dup_pos1])

Submission status: Wrong Answer

Solution code:
import sys

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

visited = set([])
hist = [-1 for _ in range(n+1)]
cur = 1
cnt = 0
d = 0

while True:
    if cnt == k:
        # print(cur)
        sys.exit()
    if hist[cur] != -1:
        d = cnt - hist[cur]
        break
    hist[cur] = cnt
    cur = a[cur]
    cnt += 1

k -= hist[cur]
index = hist[cur] + k % d
# print(hist)

for i, histi in enumerate(hist):
    if index == histi:
        print(i)
        sys.exit()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
count = 0
b = 1
for i in range(n):
    b = l[b-1]
    count += 1
    if b == 1:
        break

mod = k % count
b = 1
for i in range(mod):
    b = l[b-1]
print(b)

Submission status: Wrong Answer

Solution code:
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
for i in range(N):
    A[i] -= 1
P = dict()
k = 0
former = True
i = 0
while i < K:
    if k in P.keys() and former:
        loop = i - P[k]
        K = i + (K-i) % loop
        former = False
    else:
        P[k] = i
        k = A[k]
    i += 1
else:
    print(k+1)

Submission status: Wrong Answer

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

t = 0

for i in range(k + 1):
  t = a[t - 1]
  #print(t)

print(t)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
order = [-1]*N
crr = 0
T = 0
s = -1
order[0] = 0
for i in range(N+1):
    crr = A[crr] - 1
    if order[crr] >= 0:
        T = (i+1) - order[crr]
        s = order[crr]
        break
    order[crr] = i+1

if K <= s:
    crr = 0
    while(K):
        K -= 1
        crr = A[crr]
    print(crr+1)
else:
    k = K-s
    d = k % T
    while(d):
        d -= 1
        crr = A[crr]-1
    print(crr+1)

Submission status: Wrong Answer

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

B = [0] * N
C = []

C.append(0)
now = 0
B[0] = 1
for i in range(N):
    now = A[now] - 1
    if B[now] == 1:
        break
    else:
        C.append(now)
        B[now] = 1

mae = 0
for i in range(len(C)):
    if C[i] == now:
        mae = i
        break

ato = len(C) - 1

if K + 1 <= mae:
    print(C[K + 1] + 1)
else:
    print(C[mae + (K - mae) % (ato - mae + 1)] + 1)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a_list=list(map(int,input().split()))
tmp=a_list[0]
count=1
while count<K :
    tmp=a_list[tmp-1]
    count+=1
print(count)
print(tmp)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
閉路をmodを取って出力
閉路になっていない(回帰するなら)ならそこを出力
"""
n,k = map(int,readline().split())
lst1 = list(map(int,readline().split()))


visited = [-1]*n #modを取った時にそこにたどり着く
visited[0] = 0
now = 0
count = 1
mod = -1
lim = -1
while True:
    now = lst1[now] -1
    if visited[now] != -1: #閉路
        mod = count - visited[now]
        lim = visited[now]
        break
    if now == lst1[now]-1: #回帰
        lim = count
        mod = 0
        break
    visited[now] = count

    count += 1
    
if k <= lim:
    for i in range(n):
        if lst1[i] == k:
            print(i+1)
            exit()
else:
    if mod == 0:
        print(lim+1)
        exit()
    else:
        res = (k-lim)%mod
        for i in range(n):
            if visited[i]-lim == res:
                print(i+1)
                exit()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, k = map(int, input().split())    
a = [i - 1 for i in list(map(int, input().split()))]
# print(a)
b = []
current = 0
# cnt = 0
visited = [0 for i in range(n)]
print("a =", a)
while True:
    if visited[current] == 1:
        break 
    visited[current] = 1
    b.append(current)
    current = a[current]
print("b =", b)
m = len(b)
ans = b[k % m] + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=1
c=[1]
for i in range(k):
    b=a[b-1]
    c.append(b)
    if len(c)!=len(set(c)):
        break
e=c.index(b)
mod=k%(len(c)-e)
print(c[mod+e])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
towns=[-1]*n
towns[0]=0
current=1
for i in range(1,n+2):
  current=a[current-1]
  if towns[current-1]==-1:
    towns[current-1]=i
  else:
    loop=i-towns[current-1]
    thing=towns[current-1]
    place=current
    break
k-=thing
b=k%loop
current=place
for i in range(b):
  current=a[current-1]
  if towns[current-1]==-1:
    towns[current-1]=i
print(current)

Submission status: Wrong Answer

Solution code:
#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    tugi = [0]*n
    tugi[0] = 1
    s = 0
    cnt = 1
    while 1:
        s = a[s] - 1
        cnt += 1
        if tugi[s] > 0:
            break
        tugi[s] = cnt
    cnt -= 1
    if cnt >= k:
        for i in range(n):
            if tugi[i]==k+1:
                print(i+1)
    else:
        #s=ループスタート
        loop = [s]
        for i in range(cnt - (tugi[s]-1)-1):
            s = a[s] - 1
            loop.append(s)
        s = a[s]-1
        amari = (k-(tugi[s]-1)) % (len(loop))
        print(loop[amari]+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

now = 0
tele = [0]
i = 1
while True:
  now = A[now] - 1
  i += 1
  if now in tele:
    num = tele.index(now)
    epoch = i - num - 1
    e_list = tele[num:]
    break
  tele.append(now)
roop = int((K-num)/epoch)
amari = (K-num)%epoch
print(e_list[amari] + 1)

Submission status: Wrong Answer

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

town = [0] * n
town[0] = 1
track = [1]
now = 1
cnt = 0
while True:
    now = a[now-1]
    town[now-1] += 1
    cnt += 1
    if town[now-1] > 1:
        loop = now
        break
    track.append(now)

idx = track.index(loop)
ans = (k - idx) % (cnt - idx)
print(track[idx:][ans])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
a = list(map(int, input().split()))

length = [-1] * n
path = [-1, -1]
route = []


def func(now, depth):
    global path, length, a, route
    route.append(now)
    if length[now] == -1:
        length[now] = depth
        func(a[now]-1, depth+1)
    else:
        path = [length[now], depth - length[now]]


func(0, 0)

print(route[path[0]+(k-path[0]) % path[1]]+1)

Submission status: Wrong Answer

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

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

l=[1]

for i in a:
    b=a[l[-1]-1]
    if b==1: break
    l.append(b)

aa=len(l)

print(l[k%aa])

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n,k = myinput()
a = list(myinput())

ls = [-1]*n

ls[0] = 0
s = 0
for i in range(n):
    s = a[s] - 1
    if ls[s]<0:
        ls[s] = i + 1
        # print(ls)
    else:
        b = ls[s]
        w = (i+1) - b
        c = (k-b)%w
        g = ls.index(c+b) + 1
        print(g)
        exit()