まず、生徒 \(1\) から伝言を開始したときの答えを求めることを考えます。

これは、\(1,T _ 1,T _ {T _ 1},T _ {T _ {T _ 1}},\ldots\) と計算していき、同じ値が出るまで続けることで求められます。 同じ値が出たかどうかは、はじめすべてを false で初期化した長さ \(N\) の配列を作っておき、出現した値に対応するところを true に書き換えるなどして判定できます。 真偽値ではなく「何番目で出現したか」を配列で管理しておくと、ループの長さを求めるのが簡単になります。

次のようなアルゴリズムで生徒 \(1\) に対する答えを求めることができます。

• 長さ \(N\) の列 \(\text{ord}\) を \(\text{ord}\leftarrow(0,0,\ldots,0)\) と初期化する。
• \(a\leftarrow i,j\leftarrow1\) と初期化して、以下を繰り返す。
  • \(\text{ord}[a]\ne0\) なら、答えは \(j-\text{ord}[a]\) と求められる。繰り返しを終了する。
  • \(\text{ord}[a]\leftarrow j\) と更新する。
  • \(a\leftarrow T _ a\) と更新する。

この繰り返しは最大で \(N+1\) 回続き、すべての生徒に対してこれを行うと時間計算量は最悪で \(\Theta(N ^ 2)\) となってしまいます。

ここで、生徒 \(1\) から開始したときと生徒 \(T _ 1\) から開始したときの答えが変わらないことに着目してみます。 \(1,T _ 1,T _ {T _ 1},T _ {T _ {T _ 1}},\ldots\) のすべてに対して答えが変わらないので、生徒 \(1\) に対する答えが求められたら、生徒 \(T _ 1,\) 生徒 \(T _ {T _ 1},\ldots\) に対する答えを改めて計算する必要はありません。

よって、次のようなアルゴリズムを考えることができます。

• 長さ \(N\) の列 \(\text{ans}\) を \(\text{ans}\leftarrow(0,0,\ldots,0)\) と初期化し、長さ \(N\) の列 \(\text{ord}\) を \(\text{ord}\leftarrow(0,0,\ldots,0)\) と初期化する。
• \(i=1,2,\ldots,N\) に対して以下を繰り返す。
  • \(a\leftarrow i,\text{used}\leftarrow(i),j\leftarrow1\) と初期化して、以下を繰り返す。
    • \(\text{ans}[a]\ne0\) なら、列 \(\text{used}\) に含まれるすべての要素 \(u\) に対して、\(\text{ans}[u]\leftarrow\text{ans}[a]\) と更新し、繰り返しを終了する。
    • \(\text{ord}[a]\ne0\) なら、列 \(\text{used}\) に含まれるすべての要素 \(u\) に対して、\(\text{ans}[u]\leftarrow j-\text{ord}[a]\) と更新し、繰り返しを終了する。
    • \(\text{ord}[a]\leftarrow j\) と更新する。
    • \(a\leftarrow T _ a,\text{used}\leftarrow\text{used}+{\!\!\!}+(T _ a),j\leftarrow j+1\) と更新する。

内側のループが \(K\) 回繰り返されたとき、\(K-1\) 人の生徒について新しく答えが求まっています。 よって、内側のループは合計で \(2N\) 回しか繰り返されず、全体の計算量も \(O(N)\) となります。

内側のループをグラフ上で DFS を行うように実装してもよいでしょう。 このように実装すると、明示的に配列 \(\text{used}\) を管理しなくても関数の再帰を利用して \(\text{used}\) に含まれるすべての要素に対して \(\text{ans}\) を更新できます。

実装例は以下のようになります。 C++ の実装例では DFS を使った方針を、Python の実装例では明示的に配列 \(\text{used}\) を管理する方針をとっています。

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> T(N);
    for (int& t : T) {
        cin >> t;
        --t; // 0-indexed にしておく
    }

    vector<int> ans(N), ord(N);
    for (int i = 0; i < N; ++i) [&](this auto self, int now, int now_ord = 1) { // DFS を行う
        if (ans[now]) { // すでに答えが求められているところに到達したら
            return ans[now]; // その答えを返す
        }
        if (ord[now]) { // 今回計算したところに到達したら
            ans[now] = now_ord - ord[now]; // ループの長さを計算
            return ans[now];
        }
        ord[now] = now_ord; // 到達した順番を更新
        ans[now] = self(T[now], now_ord + 1); // 答えを DFS で求める
        return ans[now];
    }(i);

    for (int a : ans) {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}

N = int(input())

T = [t - 1 for t in map(int, input().split())] # 0-indexed にしておく

ans = [0 for _ in range(N)]
ord = [0 for _ in range(N)]

for i in range(N):
    now = i
    used = [i]
    now_ord = 1
    while True:
        if ans[now] > 0: # すでに答えが求められているところに到達したら
            for u in used:
                ans[u] = ans[now] # その答えで更新して
            break # ループを抜ける
        if ord[now] > 0: # 今回計算したところに到達したら
            for u in used:
                ans[u] = now_ord - ord[now] # ループの長さを計算して
            break # ループを抜ける
        ord[now] = now_ord # 到達した順番を更新

        # 一人進める
        now = T[now]
        used.append(now)
        now_ord += 1

print(*ans)