# [EC Final 2021] DFS Order

## 题意翻译

给定一棵以 $1$ 为根节点的树，若按**任意顺序**进行深度优先搜索，则第 $i$ 个点最小是第几个被搜到的以及最大是第几个？

## 题目描述

Prof. Pang has a rooted tree which is rooted at $1$ with $n$ nodes. These $n$ nodes are numbered from $1$ to $n$.
Now he wants to start the depth-first search at the root. He wonders for each node $v$, what is the minimum and the maximum position it can appear in the $\textbf{depth-first search order}$. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $j$-th ($1\le j\le n$) position in this order means it is visited after $j-1$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist. Prof. Pang wants to know for each node $v$, what are the minimum value and the maximum value of $j$ such that $v$ appears in the $j$-th position.
Following is a pseudo-code for the depth-first search on a rooted tree. After its execution, $\texttt{dfs\_order}$ is the depth-first search order.
```
let dfs_order be an empty list
def dfs(vertex 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)
```

## 输入输出格式

### 输入格式

The first line contains a single integer $T~(1 \le T \le 10^6)$ denoting the number of test cases.
For each test case, the first line contains an integer $n~(1 \le n \le 10 ^ 5)$. Each of the next $n-1$ lines contains two integers $x$ and $y$, indicating node $x$ is node $y$'s parent ($1\le x, y\le n$). These edges form a tree rooted at $1$.
It is guaranteed that the sum of $n$ over all test cases is no more than $10^6$.

### 输出格式

For each test case, print $n$ lines. The $i$-th line contains two integers denoting the minimum and the maximum position node $i$ can appear in the depth-first search order.

## 输入输出样例

### 输入样例 #1

```
2
4
1 2
2 3
3 4
5
1 2
2 3
2 4
1 5
```

### 输出样例 #1

```
1 1
2 2
3 3
4 4
1 1
2 3
3 5
3 5
2 5
```