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:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline



def bfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


def connection_counter(conj):                   # conj の連結成分の個数を返す。関数 bfs が必要
    cnt = 0
    visit = set()
    for start in range(N):
            if start not in visit:
                cnt += 1
                bfs(start, conj, visit)
    return cnt


def distance_list(conj, start, visit=set()):    # スタート地点からの距離の全列挙
    dist = [0]*N
    visit.add(start)
    next_set = deque([(start, 0)])
    while next_set:
        p, t = next_set.popleft()
        for q in conj[p]:
            if q in visit:
                continue
            dist[q] = t+1
            visit.add(q)
            next_set.append((q, t + 1))
    return dist


def dfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = [(start, 0)]                     # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.pop()                   # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられるる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1

#############################################################
# キャッシュにメモしながら動的計画法を行う場合など、
# 帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合には、
# 再帰関数を用いた DFS が簡明 (メモ化再帰)。
#############################################################


def dfs2(conj, p=0, goal=None, t=0, past_p=None, visit=set(), second_visit=set()):
    # global res
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        if q == goal:
            # ゴール時の処理
            # return t+1
            continue
        # p から q への引継ぎ処理
        # res[q] += res[p]
        dfs2(conj, q, goal, t+1, p, visit, second_visit)
    second_visit.add(p)
    # 帰り際の処置（壊した道を元に戻す等)
    # visit.discard(p)
    return # res


def cycle_detector(conj, p=0, t=0, dictated=False, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[]):
    visit.add(p)
    path.append(p)
    for q in sorted(conj[p]):
        if not dictated:
            if q == past_p:
                continue
        if q in second_visit:
            continue
        if q in visit:
            if not cycle:
                while path:
                    r = path.pop()
                    cycle.append(r)
                    if r == q:
                        break
            continue
        cycle_detector(conj, q, t+1, dictated, p, path, visit, second_visit, cycle)
    second_visit.add(p)
    return cycle


def tree_counter(conj, detail=False):           # 木（閉路を含まない）の個数を返す。detail = True で、閉路のリストを返す
    connection_number = 0
    cycle_list = []
    visit = set()
    second_visit = set()
    for start in range(N):
        if start not in visit:
            connection_number += 1
            cycle = cycle_detector(conj, start, visit=visit, second_visit=second_visit, cycle=[])
            if cycle:
                cycle_list.append(cycle)
    if not detail:
        return connection_number - len(cycle_list)
    else:
        return cycle_list


def path_detector(conj, p=0, t=0, past_p=None, full_path=[], visit=set(), second_visit=set(), decrement=False):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    full_path.append((p + decrement,t))
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            continue
        path_detector(conj, q, t+1, p, full_path, visit, second_visit, decrement)
    second_visit.add(p)
    full_path.append((p + decrement,t))
    return full_path

##################################################################


N, K = map(int, input().split())

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


M = N
conj = [set() for _ in range(N)]
for i in range(M):
    u = i
    v = A[i] - 1
    conj[u].add(v)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(
        reversed(cycle_detector(conj, p=0, t=0, dictated=True, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[])))
    len_cycle = len(cycle)

    p = 0
    cnt = 0
    res = 0
    if not len_cycle:
        while cnt < K:
            p = A[p] - 1
            cnt += 1
        res = p + 1
    else:
        while p != cycle[0]:
            print(p)
            p = A[p] - 1
            cnt += 1
        k = (K - cnt) % len_cycle
        res = cycle[k] + 1
print(res)

Submission status: Wrong Answer

Solution code:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline



def bfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


def connection_counter(conj):                   # conj の連結成分の個数を返す。関数 bfs が必要
    cnt = 0
    visit = set()
    for start in range(N):
            if start not in visit:
                cnt += 1
                bfs(start, conj, visit)
    return cnt


def distance_list(conj, start, visit=set()):    # スタート地点からの距離の全列挙
    dist = [0]*N
    visit.add(start)
    next_set = deque([(start, 0)])
    while next_set:
        p, t = next_set.popleft()
        for q in conj[p]:
            if q in visit:
                continue
            dist[q] = t+1
            visit.add(q)
            next_set.append((q, t + 1))
    return dist


def dfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = [(start, 0)]                     # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.pop()                   # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられるる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1

#############################################################
# キャッシュにメモしながら動的計画法を行う場合など、
# 帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合には、
# 再帰関数を用いた DFS が簡明 (メモ化再帰)。
#############################################################


def dfs2(conj, p=0, goal=None, t=0, past_p=None, visit=set(), second_visit=set()):
    # global res
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        if q == goal:
            # ゴール時の処理
            # return t+1
            continue
        # p から q への引継ぎ処理
        # res[q] += res[p]
        dfs2(conj, q, goal, t+1, p, visit, second_visit)
    second_visit.add(p)
    # 帰り際の処置（壊した道を元に戻す等)
    # visit.discard(p)
    return # res


def cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[]):
    visit.add(p)
    path.append(p)
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            if not cycle:
                while path:
                    r = path.pop()
                    cycle.append(r)
                    if r == q:
                        break
            continue
        cycle_detector(conj, q, t+1, p, path, visit, second_visit,cycle)
    second_visit.add(p)
    return cycle


def tree_counter(conj, detail=False):           # 木（閉路を含まない）の個数を返す。detail = True で、閉路のリストを返す
    connection_number = 0
    cycle_list = []
    visit = set()
    second_visit = set()
    for start in range(N):
        if start not in visit:
            connection_number += 1
            cycle = cycle_detector(conj, start, visit=visit, second_visit=second_visit, cycle=[])
            if cycle:
                cycle_list.append(cycle)
    if not detail:
        return connection_number - len(cycle_list)
    else:
        return cycle_list


def path_detector(conj, p=0, t=0, past_p=None, full_path=[], visit=set(), second_visit=set(), decrement=False):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    full_path.append((p + decrement,t))
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            continue
        path_detector(conj, q, t+1, p, full_path, visit, second_visit, decrement)
    second_visit.add(p)
    full_path.append((p + decrement,t))
    return full_path

##################################################################


N, K = map(int, input().split())

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


M = N
conj = [set() for _ in range(N)]
for i in range(M):
    u = i
    v = A[i] - 1
    conj[u].add(v)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(
        reversed(cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[])))
    len_cycle = len(cycle)
    exit()

    p = 0
    cnt = 0
    res = 0
    if not len_cycle:
        while cnt < K:
            p = A[p] - 1
            cnt += 1
        res = p + 1
    else:
        while p != cycle[0]:
            p = A[p] - 1
            cnt += 1
        k = (K - cnt) % len_cycle
        res = cycle[k] + 1
print(res)

Submission status: Wrong Answer

Solution code:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline



def bfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


def connection_counter(conj):                   # conj の連結成分の個数を返す。関数 bfs が必要
    cnt = 0
    visit = set()
    for start in range(N):
            if start not in visit:
                cnt += 1
                bfs(start, conj, visit)
    return cnt


def distance_list(conj, start, visit=set()):    # スタート地点からの距離の全列挙
    dist = [0]*N
    visit.add(start)
    next_set = deque([(start, 0)])
    while next_set:
        p, t = next_set.popleft()
        for q in conj[p]:
            if q in visit:
                continue
            dist[q] = t+1
            visit.add(q)
            next_set.append((q, t + 1))
    return dist


def dfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = [(start, 0)]                     # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.pop()                   # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられるる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1

#############################################################
# キャッシュにメモしながら動的計画法を行う場合など、
# 帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合には、
# 再帰関数を用いた DFS が簡明 (メモ化再帰)。
#############################################################


def dfs2(conj, p=0, goal=None, t=0, past_p=None, visit=set(), second_visit=set()):
    # global res
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        if q == goal:
            # ゴール時の処理
            # return t+1
            continue
        # p から q への引継ぎ処理
        # res[q] += res[p]
        dfs2(conj, q, goal, t+1, p, visit, second_visit)
    second_visit.add(p)
    # 帰り際の処置（壊した道を元に戻す等)
    # visit.discard(p)
    return # res


def cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[]):
    visit.add(p)
    path.append(p)
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            if not cycle:
                while path:
                    r = path.pop()
                    cycle.append(r)
                    if r == q:
                        break
            continue
        cycle_detector(conj, q, t+1, p, path, visit, second_visit,cycle)
    second_visit.add(p)
    return cycle


def tree_counter(conj, detail=False):           # 木（閉路を含まない）の個数を返す。detail = True で、閉路のリストを返す
    connection_number = 0
    cycle_list = []
    visit = set()
    second_visit = set()
    for start in range(N):
        if start not in visit:
            connection_number += 1
            cycle = cycle_detector(conj, start, visit=visit, second_visit=second_visit, cycle=[])
            if cycle:
                cycle_list.append(cycle)
    if not detail:
        return connection_number - len(cycle_list)
    else:
        return cycle_list


def path_detector(conj, p=0, t=0, past_p=None, full_path=[], visit=set(), second_visit=set(), decrement=False):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    full_path.append((p + decrement,t))
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            continue
        path_detector(conj, q, t+1, p, full_path, visit, second_visit, decrement)
    second_visit.add(p)
    full_path.append((p + decrement,t))
    return full_path

##################################################################


N, K = map(int, input().split())

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


M = N
conj = [set() for _ in range(N)]
for i in range(M):
    u = i
    v = A[i] - 1
    conj[u].add(v)

p = 0
cnt = 0
if K <= N:
    while cnt + 1 <= K:
        p = A[p] - 1
        cnt += 1
    res = p + 1
else:
    cycle = list(
        reversed(cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[])))
    len_cycle = len(cycle)

    p = 0
    cnt = 0
    res = 0
    if not len_cycle:
        while cnt < K:
            p = A[p] - 1
            cnt += 1
        res = p + 1
    else:
        while p != cycle[0]:
            p = A[p] - 1
            cnt += 1
        k = (K - cnt) % len_cycle
        res = cycle[k] + 1
    print(res)

Submission status: Wrong Answer

Solution code:
#####################################################################################################
##### 深さ優先探索 幅優先探索　（グラフ）
#####################################################################################################

'''

キューに頂点を入れる回数は各々高々１回のみ。
各辺を使う回数は高々一回のみ（辺を戻るような探索は枝切りされている）
結果として、計算量はO(N + M)

'''

from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline



def bfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = deque([(start, 0)])              # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.popleft()               # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1


def connection_counter(conj):                   # conj の連結成分の個数を返す。関数 bfs が必要
    cnt = 0
    visit = set()
    for start in range(N):
            if start not in visit:
                cnt += 1
                bfs(start, conj, visit)
    return cnt


def distance_list(conj, start, visit=set()):    # スタート地点からの距離の全列挙
    dist = [0]*N
    visit.add(start)
    next_set = deque([(start, 0)])
    while next_set:
        p, t = next_set.popleft()
        for q in conj[p]:
            if q in visit:
                continue
            dist[q] = t+1
            visit.add(q)
            next_set.append((q, t + 1))
    return dist


def dfs(conj, start, goal=None, visit=set()):
    visit.add(start)                            # スタート地点はすでに訪れている
    next_set = [(start, 0)]                     # 次に進む候補を列挙する。スタック（右から取り出す = pop）だと深さ優先になり、キュー（左から取り出す = popleft）だと幅優先になる
                                                # 第一成分はスタート地点、第二成分は時刻を表す。
    while next_set:                             # p = [] になったら止める
        p, t = next_set.pop()                   # 要素を消去して、消去した要素を出力
        for q in conj[p]:                       # 頂点 p から進める経路の候補から一つ選ぶ
            if q in visit:                      # 一度訪れていた場合は進まない
                continue
            if q == goal:                       # ゴールがあるならば、ここで判定
                return t + 1                    # 経路の長さは t + 1 で与えられるる
            visit.add(q)                        # 頂点 q に一度訪れた事をメモ (for の前に書くと、ここで選ばれた q が最短であるはずなのに、違う経路でvisit = Trueを踏んでしまう可能性がある)
            next_set.append((q, t + 1))         # p から q へと移動。時刻を 1 進める
    return -1

#############################################################
# キャッシュにメモしながら動的計画法を行う場合など、
# 帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合には、
# 再帰関数を用いた DFS が簡明 (メモ化再帰)。
#############################################################


def dfs2(conj, p=0, goal=None, t=0, past_p=None, visit=set(), second_visit=set()):
    # global res
    visit.add(p)
    for q in conj[p]:
        if q == past_p:
            # 逆流した際の処理
            continue
        if q in second_visit:
            # 帰り道に訪れた際の処理
            continue
        if q in visit:
            continue
        if q == goal:
            # ゴール時の処理
            # return t+1
            continue
        # p から q への引継ぎ処理
        # res[q] += res[p]
        dfs2(conj, q, goal, t+1, p, visit, second_visit)
    second_visit.add(p)
    # 帰り際の処置（壊した道を元に戻す等)
    # visit.discard(p)
    return # res


def cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[]):
    visit.add(p)
    path.append(p)
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            if not cycle:
                while path:
                    r = path.pop()
                    cycle.append(r)
                    if r == q:
                        break
            continue
        cycle_detector(conj, q, t+1, p, path, visit, second_visit,cycle)
    second_visit.add(p)
    return cycle


def tree_counter(conj, detail=False):           # 木（閉路を含まない）の個数を返す。detail = True で、閉路のリストを返す
    connection_number = 0
    cycle_list = []
    visit = set()
    second_visit = set()
    for start in range(N):
        if start not in visit:
            connection_number += 1
            cycle = cycle_detector(conj, start, visit=visit, second_visit=second_visit, cycle=[])
            if cycle:
                cycle_list.append(cycle)
    if not detail:
        return connection_number - len(cycle_list)
    else:
        return cycle_list


def path_detector(conj, p=0, t=0, past_p=None, full_path=[], visit=set(), second_visit=set(), decrement=False):   # 距離と探索経路を返す。デクリメントされている場合は、decrement=True にする
    visit.add(p)
    full_path.append((p + decrement,t))
    for q in sorted(conj[p]):
        if q == past_p:
            continue
        if q in second_visit:
            continue
        if q in visit:
            continue
        path_detector(conj, q, t+1, p, full_path, visit, second_visit, decrement)
    second_visit.add(p)
    full_path.append((p + decrement,t))
    return full_path

##################################################################

N, K = map(int, input().split())
M = N
A = list(map(int, input().split()))

conj = [set() for _ in range(N)]
for i in range(M):
    u = i
    v = A[i] - 1
    conj[u].add(v)
    conj[v].add(u)                            # 無効グラフの場合は消す


cycle = list(reversed(cycle_detector(conj, p=0, t=0, past_p=None, path=[], visit=set(), second_visit=set(), cycle=[])))
len_cycle = len(cycle)

p = 0
cnt = 0
if not len_cycle:
    while cnt < K:
        p = A[p] - 1
        cnt += 1
    print(p)
    exit()
else:
    while p != cycle[0] and cnt < K:
        p = A[p] - 1
        cnt += 1
k = (K-cnt)%len_cycle
print(cycle[k] + 1)

Submission status: Wrong Answer

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

town = 1
once = [0]*(n+1)

for i in range(n):
  if once[town]==0:
    once[town] = 1
  else:
    break
  town = A[town]

rt = A[town]
roop = 1
while rt != town:
  rt = A[rt]
  roop += 1

rt = 1
bf = 0
while rt != town:
  rt = A[rt]
  bf += 1  

if roop<k or bf<k:
  K = (k-bf)%roop + bf
else:
  K = k

town = 1
for _ in range(K):
  town = A[town]

print(town)

Submission status: Wrong Answer

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

town = 1
once = [0]*(n+1)

for i in range(n):
  if once[town]==0:
    once[town] = 1
  else:
    break
  town = A[town]

rt = A[town]
roop = 1
while rt != town:
  rt = A[rt]
  roop += 1

rt = 1
bf = 0
while rt != town:
  rt = A[rt]
  bf += 1  

K = (k-bf)%roop + bf
town = 1
for _ in range(K):
  town = A[town]

print(town)

Submission status: Wrong Answer

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

A = [0] + A

visited = [1]
now = 1
while True:
  next = A[now]
  if next in visited:
    break
  visited.append(next)
  now = next

initial = visited.index(next)
cycle = len(visited[initial:])

residual = (K - initial) % cycle
print(visited[initial+residual])

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    to = [[None]*n for _ in range(60)]
    to[0] = a[:]
    for i in range(1, 60):
        for j in range(n):
            to[i][j] = to[i-1][to[i-1][j]-1]
    p = 1
    for i in range(59, -1, -1):
        num = 2 << i
        if k >= num:
            k -= num
            p = to[i][p-1]
    print(p)
            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# Problem D - Teleporter

# input
N, K = map(int, input().split())
a_nums = list(map(int, input().split()))

# initialization
a_visit = [0]*N
point = a_nums[0]
a_visit[0] = 1
visit_count = 1
loop_count = 0

# count 1
while visit_count<K:
    visit_count += 1
    if a_visit[point-1]!=0:
        loop_count = K%(visit_count-a_visit[point-1])
        break
    else:
        a_visit[point-1] = visit_count
        point = a_nums[point-1]

# count 2
for i in range(loop_count):
    point = a_nums[point]

# output
print(point)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
#nは高々2*10**5だから回せる。kは大きすぎて無理
#一周してあまりをとるべき
a_new=[]
for i, k in enumerate(a):
  a_new.append([i,k])
c=np.array(a_new).reshape(-1,2)
for i in range(len(c)):
  c[i][0]+=1
#ここまで形を整える
print(c)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
city = list(map(int, input().split()))
now = city[0]
li = [1]

for i in range(K - 1):
    li.append(now)
    now = city[now - 1]
    K -= 1
    if now in li:
        start_city = li.index(now)
        li = li[start_city:]
        K = (K - 1) % len(li)
        print (li[K])
        break

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
town=[0]*n
info=[1]
now=1
while town[now-1]==0:
    town[now-1]+=1
    now=a[now-1]
    info.append(now)
loop_list=list(info[info.index(now):-1])
loop_len=len(loop_list)
before_loop_list=list(info[:info.index(now)])
print(town)
print(info)
if k<len(before_loop_list):
    print(before_loop_list[k])
else:
    print(loop_list[((k-len(before_loop_list))%loop_len)])

Submission status: Wrong Answer

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


b=[1]
d=set()
d.add(1)
e=1
while n==n:
  if a[e] in d:
    e=a[e]
    break
  b.append(a[e])
  d.add(a[e])
  e=a[e]
print(b[(k-b.index(e))%(len(b)-b.index(e))+b.index(e)])

Submission status: Wrong Answer

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


b=[1]
d=set()
d.add(1)
e=1
while n==n:
  if a[e] in d:
    e=a[e]
    break
  b.append(a[e])
  d.add(a[e])
  e=a[e]
print(b[(k-len(d))%(len(d)-b.index(e))+b.index(e)])

Submission status: Wrong Answer

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

r=[0]*n
h=i=0
while i+1 not in r:
    r[h] = i+1
    if k == h:
        print(i+1)
        sys.exit()
    i = a[i] - 1
    h += 1

del r[h:]
print(r)
p = r.index(i+1)
q = len(r)-p
r_q = r[p:]


j = (k+1-p)%q
print(r_q[j-1])

Submission status: Wrong Answer

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

r=[0]*n
h=i=0
while i+1 not in r:
    r[h] = i+1
    if k == h:
        print(i+1)
        sys.exit()
    i = a[i] - 1
    h += 1

del r[h+1:]

p = r.index(i+1)
q = len(r)-p
r_q = r[p:]


j = (k+1-p)%q
print(r_q[j-1])

Submission status: Wrong Answer

Solution code:
import sys
def Ii():return int(sys.stdin.buffer.read())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n,k = Mi()
a = Li()
b = [1]
b.append(a[0])
flag = False
for i in range(n):
  for j in range(len(b)):
    if b[j] == a[b[-1]-1]:
      flag = True
      break
  if flag: 
    break
    
  b.append(a[b[-1]-1])

roop = len(b)-j
roopk = k%roop

print(b[roopk])