#P2544. 树的广度优先遍历

树的广度优先遍历

题目描述

给定一棵根节点为 11 的有根树,请输出对其进行广度优先搜索过程中,依次经过的节点和其到根节点的距离。

两点之间的距离定义为:联通两点的路径中经过的最小边数。

输入格式

第一行输入一个整数 n(1n1000)n(1 \leq n \leq 1000),代表节点数。

第二行输入 n1n-1 个整数,第 ii 个整数代表节点 i+1i+1的父节点。

输出格式

输出 nn 行,每行输出 22 个整数,代表BFS过程中依次经过的节点和到根节点的距离,相邻两个数之间以空格分开。

样例

10
1 1 3 3 4 1 7 1 4
1 0
2 1
3 1
7 1
9 1
4 2
5 2
8 2
6 3
10 3