Overview

This problem asks us to find the length of the “loop (cycle)” that each vertex eventually reaches in a graph where exactly one directed edge goes out from each vertex (a Functional Graph).

Analysis

Since each student passes the message to exactly one other person, starting from any student, you will always eventually reach a loop.

Naive Approach and Its Limitations

One possible method is to simulate the process one by one for every student \(i\). However, in the worst case, a single traversal takes \(O(N)\) time, resulting in \(O(N^2)\) total time. Under the constraint \(N = 2 \times 10^5\), this will not fit within the time limit (TLE).

Hints Toward an Efficient Solution

The structure of this graph has the following characteristics: 1. Every path eventually reaches a loop: No matter which vertex you start from, you will eventually enter a loop and never leave it. 2. Vertices on the same path share the same result: If there is a loop reachable from student \(A\), then student \(B\) who lies on the path from \(A\) to that loop will also reach the same loop. Therefore, previously computed results can be reused.

By leveraging these characteristics and recording (memoizing) the results of previously visited vertices during traversal, we only need to examine each vertex a constant number of times.

Algorithm

We scan all vertices while managing each vertex’s state using the following three states:

1. Unvisited (0): Has not been explored yet.
2. In Progress (1): Currently included in the exploration path from the current starting point.
3. Completed (2): The loop it reaches has already been determined.

Detailed Procedure

1. Pick a student \(i\) that is still “Unvisited” and start the exploration.
2. While following “Unvisited” students, mark each as “In Progress” and record the path (the order of visited vertices).
3. Repeat until the next student to visit is in one of the following states:
   • Encountered an “In Progress” student: This means a new loop has been discovered. By checking the position at which that student appeared in the path, we can calculate the loop length (current path length - position of that student).
   • Encountered a “Completed” student: This means we have merged into an already-analyzed structure. The loop length that this student ultimately reaches is already known, so we simply reuse it.
4. Mark all students on the explored path as “Completed” and record the determined loop size for each.

By performing this for all students, we can efficiently find the answer for every student.

Complexity

• Time Complexity: \(O(N)\) Each vertex and each edge is traversed a constant number of times (only transitions from “Unvisited” to “In Progress” and from “In Progress” to “Completed”), so the processing completes in linear time with respect to the number of students \(N\).
• Space Complexity: \(O(N)\) \(O(N)\) memory is used to store the destination array, the visit state array, the result array, and the exploration path.

Implementation Notes

• Avoiding Recursion: When performing deep traversals in Python, using recursive functions may cause a stack overflow (RecursionError), so an iterative implementation using while loops is safer.

• Conversion to 0-indexed: The input student numbers range from \(1\) to \(N\), but handling them as \(0\) to \(N-1\) within the program makes array index operations smoother.

• Recording Positions in the Path: To instantly compute the loop length, it is efficient to record “which student appeared at which position” in the current exploration path using a dictionary (path_map) or similar data structure.

  Source Code

import sys

def solve():
    # 入力を一度にすべて読み込みます
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 生徒の数 N
    n = int(data[0])
    
    # 各生徒 i のメッセージの渡し先 T_i
    # 0-indexed に変換して管理します（生徒 1 はインデックス 0、生徒 2 はインデックス 1 ...）
    t = [int(x) - 1 for x in data[1:]]
    
    # 各生徒から開始したときの伝言ループメンバーの人数を格納する配列
    ans = [0] * n
    
    # 訪問状態を管理する配列
    # 0: 未訪問, 1: 現在の探索パスに含まれている, 2: 探索完了済み（確定済み）
    visited = [0] * n
    
    for i in range(n):
        # 既に探索済みの生徒はスキップ
        if visited[i] == 2:
            continue
        
        curr = i
        path = []
        # 現在の探索パス内での生徒の出現位置を記録する辞書
        path_map = {}
        
        # メッセージの伝言をたどる
        while visited[curr] == 0:
            path_map[curr] = len(path)
            path.append(curr)
            visited[curr] = 1
            curr = t[curr]
        
        # 停止したとき、curr は「過去に既にメッセージを受け取ったことのある生徒」
        if visited[curr] == 1:
            # 現在の探索パス内で既に訪れた生徒に到達した場合（新しいループを発見）
            # ループの開始位置を取得
            cycle_start_idx = path_map[curr]
            # ループに含まれる生徒の人数を計算
            cycle_len = len(path) - cycle_start_idx
            # この探索パス上のすべての生徒は、最終的にこのループに到達する
            for node in path:
                ans[node] = cycle_len
        else:
            # 既に探索完了済みの生徒に到達した場合（既存の構造に合流）
            # その生徒が最終的に到達するループの人数をそのまま利用
            cycle_len = ans[curr]
            for node in path:
                ans[node] = cycle_len
        
        # 今回たどったパス上のすべての生徒を探索完了済み（visited = 2）にする
        for node in path:
            visited[node] = 2
            
    # 結果をスペース区切りで出力
    print(*(ans))

if __name__ == '__main__':
    solve()

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