rt:

【pty2021】甜甜的花环

题目描述

甜甜马上就要过生日了，胖头鱼打算做一个花环送给甜甜作为生日礼物，他采集了$n$朵花，并从$1$开始编号。

每朵花由花朵和连着花朵的花茎两部分组成，花茎有两头，胖头鱼通过将花茎的另一头粘到其他花的花朵上，就制作出了花环。所以，花环由一个主环和主环周围的一些花枝组成。

我们可以将花朵看成点，花茎看成长为$1$的线条，现在甜甜想知道，在这个花环中，每朵花到主环的距离是多少，但是她不知道怎么算，所以只好把这个任务交给你了。

输入格式

第一行包含整数$n$。
第二行包含$n$个整数，第$j$个整数$a_j$表示编号为$j$的花连到了编号为$a_j$的花上。

输出格式

输出$n$个整数，第$i$个整数表示编号为$i$的花到主环的距离，整数之间用空格隔开。

样例 #1

样例输入 #1

6
2 4 1 5 2 1

样例输出 #1

1 0 2 0 0 2

样例 #2

样例输入 #2

6
2 3 2 1 4 3

样例输出 #2

1 0 0 2 3 1

提示

样例解释

【样例 1 解释】

如下图所示

$2$、$4$、$5$构成环，$1$连在$2$上，$3$、$6$连在$1$上。

【样例 2 解释】

如下图所示

$2$和$3$构成环，$1$连着$2$，$4$连着$1$，$5$连着$4$，$6$连着$3$。

数据规模

对于60%的数据，最多只有$1$朵花不在主环上；
对于80%的数据，$1 ≤ n ≤ 5000$；
对于100%的数据，$1 ≤ n ≤ 10^5$。