/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君のクラスには N 人の生徒がおり、生徒には 1 から N までの番号が付けられています。このクラスでは、伝言ゲームが行われます。
各生徒 i（1 \leq i \leq N）には、メッセージを次に渡す相手の生徒番号 T_i がちょうど1人決まっています（T_i \neq i）。
伝言ゲームは以下のように進行します。まず開始生徒 s を選びます。a_0 = s とし、k \geq 0 に対して a_{k+1} = T_{a_k} で列 a_0, a_1, a_2, \ldots を定めます。
はじめに a_0 を「訪問済み」とします。その後、k = 1, 2, \ldots の順に以下を繰り返します。
- a_k が既に訪問済みであれば、伝言はそこで停止する。
- そうでなければ、a_k を訪問済みとし、次の k に進む。
生徒数は有限なので、伝言は必ず有限回のステップで停止します。
停止時に到達した生徒（すなわち、停止時の a_k）を v とおきます。v は過去に一度訪問済みとなった生徒であり、v から T を繰り返し適用していくと再び v に戻ります。すなわち、v, T_v, T_{T_v}, \ldots とたどっていくと、いつか再び v に到達します。この v から出発して v に戻るまでの経路上に含まれる生徒の人数（v 自身を含む）を、開始生徒 s に対する伝言ループの長さと呼びます。
生徒 1 から伝言を開始した場合、生徒 2 から開始した場合、……、生徒 N から開始した場合のそれぞれについて、伝言ループの長さを求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq T_i \leq N
- T_i \neq i（1 \leq i \leq N）
- 入力はすべて整数である。
入力
N T_1 T_2 \ldots T_N
- 1 行目には、生徒の人数を表す整数 N が与えられる。
- 2 行目には、各生徒 i のメッセージの渡し先を表す整数 T_i が、スペース区切りで N 個与えられる。
出力
C_1 C_2 \ldots C_N
- 生徒 i から伝言を開始したときの伝言ループの長さを C_i として、i = 1, 2, \ldots, N の順にスペース区切りで 1 行で出力せよ。
入力例 1
4 2 3 4 2
出力例 1
3 3 3 3
入力例 2
7 2 3 1 5 6 4 5
出力例 2
3 3 3 3 3 3 3
入力例 3
10 2 3 2 5 4 7 8 6 8 1
出力例 3
2 2 2 2 2 3 3 3 3 2
Score : 366 pts
Problem Statement
There are N students in Takahashi's class, numbered from 1 to N. The class plays a message-passing game (telephone game).
For each student i (1 \leq i \leq N), there is exactly one designated student T_i to whom they pass the message (T_i \neq i).
The game proceeds as follows. First, a starting student s is chosen. Let a_0 = s, and for k \geq 0, define the sequence a_0, a_1, a_2, \ldots by a_{k+1} = T_{a_k}.
Initially, a_0 is marked as "visited." Then, for k = 1, 2, \ldots in order, the following is repeated:
- If a_k is already visited, the message stops there.
- Otherwise, mark a_k as visited and proceed to the next k.
Since the number of students is finite, the message always stops after a finite number of steps.
Let v denote the student reached when the process stops (i.e., a_k at the time of stopping). The student v was previously marked as visited, and repeatedly applying T starting from v will eventually return to v. That is, following the path v, T_v, T_{T_v}, \ldots will eventually reach v again. The number of students on the path starting from v and returning to v (including v itself) is called the message loop length for starting student s.
For each case where the message starts from student 1, student 2, ..., student N, find the message loop length.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq T_i \leq N
- T_i \neq i (1 \leq i \leq N)
- All input values are integers.
Input
N T_1 T_2 \ldots T_N
- The first line contains an integer N, representing the number of students.
- The second line contains N integers T_i, separated by spaces, representing the recipient of each student i's message.
Output
C_1 C_2 \ldots C_N
- Let C_i be the message loop length when the message starts from student i. Output C_i for i = 1, 2, \ldots, N in order, separated by spaces, on a single line.
Sample Input 1
4 2 3 4 2
Sample Output 1
3 3 3 3
Sample Input 2
7 2 3 1 5 6 4 5
Sample Output 2
3 3 3 3 3 3 3
Sample Input 3
10 2 3 2 5 4 7 8 6 8 1
Sample Output 3
2 2 2 2 2 3 3 3 3 2