题目描述

给定一棵根节点为 $1$ 的有根树，请输出从根节点开始，对其进行深度优先搜索过程中，依次经过的节点与其对应的深度。定义根节点的深度为 $1$。

若某个节点有多个子节点，应首先输出编号更小的节点。

输入格式

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

第二行输入 $n-1$ 个整数，第 $i$ 个整数代表节点 $i+1$的父节点。

输出格式

输出 $n$ 行，每行两个整数，代表DFS过程中依次经过的节点和对应的深度。

样例

10
1 1 3 3 4 1 7 1 4

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

样例解释

样例中图如下。