思路

将问题建模为带权图最短路：

• 从 $i$ 到 $a_i$ 的有向边，权重为 $0$。
• 从 $i$ 到 $i-1$、$i+1$ 的边（若存在），权重为 $1$。 要求从 $1$ 到所有点的最短路，权值和等于步行次数。

由于边权只为 $0$ 或 $1$，使用 $0$-$1$ BFS：

题目内容

在一片神奇的魔法森林中，有 $n$ 个魔法节点，每个节点都有一个传送门。第 $i$ 个节点的传送门会把你传送到 $a_i$ 号节点。

多多每次可以选择坐传送门从 $i$ 节点传送到 $a_i$ 节点，或者选择步行到相邻的节点 $i-1$ 或 $i+1$ 节点。

当然多多是个喜欢偷懒的人，所以它能坐传送门就尽量不步行。

现在多多从 $1$ 号节点出发，想知道到达每个节点需要经过的最少步行次数。

输入描述

输入两行，第一行包含一个数字 $n(1<=n<=100000)$ ，表示有 $n$ 个节点。

接下来一行 $n$ 个数字，每个数字 $a_i(1<=a_i<=n)$ ，表示 $i$ 节点的传送门可以传送到 $a_i$ 节点，注意 $a_i$ 可能等于 $i$

输出描述

输出一行包含 $n$ 个数字，第 $i$ 个数字 $ans_i$ ，表示从 $1$ 号节点到 $i$ 号节点的最少步行次数

样例1

输入

3
1 2 3

输出

0 1 2

样例2

输入

4
4 2 3 1

输出

0 1 1 0