题目描述

给定一张 $n$ 个点的有向图，每个点有且只有一个后继，第 $i$ 个点的后继编号为 $t_i$。依次从每个点出发，沿着图中给定的后继前进，可以证明经过有限次移动后，必然会陷入一个循环。

请分别求出，从每个点出发后，经过多少步后会陷入循环，即返回到一个曾经路过的结点。

输入格式

第一行：单个整数表示 $n$； 第二行：$n$ 个整数表示 $t_1,t_2,\dots,t_n$。

输出格式

共 $n$ 行，其中第 $i$ 行表示从 $i$ 号点出发，经过多少步之后，将返回一个曾经经过的结点。

4
2 1 1 4

2 
2 
3 
1

样例解释 1

1与2构成一个环, 4独自构成一个环

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 3000$，
• 对于 $60\%$ 的数据，$1\leq n\leq 100,000$，
• 对于 $100\%$ 的数据，$1\leq n\leq 500,000$。