链接: https://cses.fi/problemset/task/1160

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你正在玩一个由 $n$ 个行星组成的游戏。每个行星都有一个通向另一个行星（或自身）的传送器。

你从一个行星出发，然后不断通过传送器旅行，直到到达一个你此前已经访问过的行星。

你的任务是针对每个行星，计算如果你从该行星出发，总共需要进行多少次传送。

输入

第一行输入包含一个整数 $n$：行星的数量。行星编号为 $1,2,\dots,n$。

第二行包含 $n$ 个整数 $t_1,t_2,\dots,t_n$：对应每个行星，传送器的目的地。有可能 $t_i=i$。

输出

按照题意输出 $n$ 个整数。

数据范围

$1 \le n \le 2 \cdot 10^5$ $1 \le t_i \le n$

样例输入

5
2 4 3 1 4

样例输出

3 3 1 3 4