#CS1751. 行星循环

行星循环

题目背景

翻译自 CSES-1751 题。

题目描述

你正在玩一个由 n 个行星组成的游戏。每个行星都有一个传送门，传送到另一个行星（或者是它自己）。

你从一个行星出发，经过传送门，直到到达一个已经访问过的行星。

你的任务是计算从每个行星出发时，经过多少次传送才能到达已经访问过的行星。

输入格式

第一行包含一个整数 n：表示行星的数量。行星编号为 1,2,…,n1,2,…,n1,2,…,n。

第二行包含 n 个整数 t1,t2,…,tnt_1,t_2,…,t_nt1​,t2​,…,tn​：表示每个行星的传送门目的地。如果 ti=it_i = iti​=i，则表示该行星的传送门指向自己。

输出格式

输出 n 个整数，表示从每个行星出发，经过多少次传送会到达已经访问过的行星。

样例

5
2 4 3 1 4

3 3 1 3 4

说明/提示

$1 \leq n \leq 2 \cdot 10^5$

1≤ti≤n1 \leq t_i \leq n1≤ti​≤n。