Overview

This problem is a simulation problem where, given a railway line where each station has exactly one predetermined next destination, you start from station \(1\) and need to determine how many stations you visit before arriving at the destination station \(N\).

Analysis

The key point of this problem is that “the destination from each station is fixed to exactly one station.”

When you arrive at station \(i\), you always proceed to station \(P_i\) next. In other words, the route from station \(1\) to station \(N\) is a single path with no room for choice. Therefore, by updating the “current station” according to the problem’s instructions and repeating the movement until reaching station \(N\), we can derive the correct answer.

Checking the constraints, the number of stations \(N\) is at most \(2 \times 10^5\). In the worst case, you pass through every station exactly once, but even then the number of computations is around \(2 \times 10^5\). This is well within the time limit of typical programming languages (usually about 2 seconds).

Algorithm

We perform the simulation with the following steps:

1. Initialize a variable curr pointing to the current station to \(1\).
2. Initialize a variable count that counts the number of visited stations to \(1\) (since it includes the starting station \(1\)).
3. Repeat the following process until curr equals \(N\):
   • Update curr to \(P_{curr}\), the destination from the current station.
   • Increment count by \(1\).
4. Output the final value of count.

Complexity

• Time Complexity: \(O(N)\)
  • Since at most \(N\) stations are visited from station \(1\) to station \(N\), the loop runs at most \(N\) times.
• Space Complexity: \(O(N)\)
  • Memory proportional to the number of stations is used to store each station’s destination \(P_i\) in a list (array).

Implementation Notes

• Index Correspondence: The problem gives station numbers from \(1\) to \(N\), but lists in many programming languages (such as Python) are 0-indexed. When storing the destination \(P_i\) of station \(i\) in a list p, note that the next station from station curr is p[curr - 1].

• Reading Input: Since \(N\) can be large, it is recommended to read input efficiently. In Python, you can use sys.stdin.read().split() to retrieve a large number of values all at once.

  Source Code

import sys

def main():
    # 入力をすべて読み込み、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 駅の数 N
    n = int(input_data[0])
    # 各駅からの行き先 P_i (i=1 から N-1 まで)
    # P[i-1] が駅 i からの行き先に対応するようにリスト化します
    p = list(map(int, input_data[1:]))
    
    # 現在の駅 (1からスタート)
    curr = 1
    # 訪れた駅の数 (出発駅を含むため1で初期化)
    count = 1
    
    # 目的地である駅 N に到着するまで繰り返します
    while curr != n:
        # 駅 i からの行き先は P_i です。
        # リスト p は 0-indexed なので、駅 curr からの行き先は p[curr - 1] です。
        curr = p[curr - 1]
        # 訪れた駅の数をカウント
        count += 1
    
    # 結果を出力
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-thinking.