DFS Order Position Range in a Tree

Professor Pang has a rooted tree with n nodes, numbered from 1 to n, where node 1 is the root. He intends to perform a depth-first search (DFS) from the root according to the following pseudo-code:

let dfs_order be an empty list
def dfs(x):
append x to the end of dfs_order
for (each son y of x): // sons can be iterated in arbitrary order
dfs(y)
dfs(root)

</p>

Because the order in which the children (sons) of a node are visited can be chosen arbitrarily, multiple DFS orders exist. For each node \( v \), Prof. Pang wonders what are the minimum and maximum possible positions that \(v\) can have in any DFS order. Here, if \(v\) appears as the \(j\)-th node in the DFS order, it means that \(v\) is visited after \(j-1\) other nodes.

Observation: To achieve the minimum position for a node \(v\), one may always choose, at every step in the DFS, to first follow the unique path from the root to \(v\). This gives \(v\) a minimum position equal to its depth in the tree (with the root having depth 1).

To achieve the maximum position for \(v\), one may postpone visiting \(v\) as long as possible by processing, at each ancestor, all other children (and their entire subtrees) before following the branch that leads to \(v\). Formally, if \(u\) is the parent of \(v\) and \(\text{size}(u)\) denotes the number of nodes in the subtree of \(u\), then the maximum possible DFS position for \(v\) can be computed recursively as:

\( \text{maxPos}(v) = \text{maxPos}(u) + \big(\text{size}(u) - \text{size}(v)\big) \)

with \(\text{maxPos}(1)=1\) for the root.

Your task is to compute for each node \(v\) (from 1 to \(n\)) the minimum and maximum positions it can appear in the DFS order.

inputFormat

The first line contains an integer \( n \) (\(1\le n\le 10^5\)), the number of nodes in the tree. The second line contains \( n-1 \) integers. For each \( i \) (\(2\le i\le n\)), the \( i \)-th integer indicates the parent of node \( i \). Note that node 1 is the root.

outputFormat

Output \( n \) lines. The \( i \)-th line should contain two integers: the minimum and maximum possible positions at which node \( i \) can appear in a DFS order.

sample

3
1 1

1 1
2 3
2 3

</p>