分数: 366 分
问题陈述
有 N 高桥班的学生,编号为 1 to N。全班同学玩一个传递消息的游戏(电话游戏)。
对于每个学生 i (1 \leq i \leq N),只有一名指定学生 T_i 他们将消息传递给谁(T_i \neq i).
游戏进行如下。首先,一个入门学生 选择 s 。让 a_0 = s,并且对于 k \geq 0,定义序列 a_0, a_1, a_2, \ldots by a_{k+1} = T_{a_k}.
最初, a_0 被标记为“已访问”。那么,对于 k = 1, 2, \ldots 按顺序重复以下内容:
- If a_k 已被访问,消息停在那里。
- 否则,标记 a_k 已访问并继续下一步 k.
由于学生的数量是有限的,因此消息总是在有限的步骤之后停止。
让 v 表示进程停止时到达的学生(即, a_k 停止时)。学生 v 之前已标记为已访问,并重复申请 T 从 v 最终将返回 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
- 第一行包含一个整数 N,代表学生人数。
- 第二行包含 N 整数 T_i,用空格分隔,代表每个学生的接收者 i的消息。
输出
C_1 C_2 \ldots C_N
- 让 C_i 是消息从学生开始时的消息循环长度 i。输出 C_i 为 i = 1, 2, \ldots, N 按顺序排列,用空格分隔,在一行上。
示例输入 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