该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

庞教授有一棵以 $1$ 为根的树，这棵树有 $n$ 个节点。这 $n$ 个节点的编号从 $1$ 到 $n$。

现在他想从根节点开始进行深度优先搜索。他想知道对于每个节点 $v$，它在深度优先搜索顺序中出现的最小和最大位置。深度优先搜索顺序是指在深度优先搜索过程中访问节点的顺序。一个节点出现在这个顺序中的第 $j$ 个位置（$1 \le j \le n$）意味着它是在 $j-1$ 个其他节点之后被访问的。由于一个节点的子节点可以以任意顺序进行迭代，因此存在多种可能的深度优先顺序。庞教授想知道对于每个节点 $v$，使得 $v$ 出现在第 $j$ 个位置的最小值和最大值分别是多少。

输入格式

第一行包含一个整数 $T~(1 \le T \le 10^6)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n~(1 \le n \le 10 ^ 5)$。接下来的 $n-1$ 行中的每一行包含两个整数 $x$ 和 $y$，表示节点 $x$ 是节点 $y$ 的父节点（$1\le x, y\le n$）。这些边形成了一棵以 $1$ 为根的树。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出 $n$ 行。第 $i$ 行包含两个整数，表示节点 $i$ 在深度优先搜索顺序中出现的最小和最大位置。

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

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