题目描述

有一棵树，其节点编号为 $1$ 到 $n$。树的根节点固定为 $1$。

现在对这棵树进行深度优先搜索（DFS）。我们知道，DFS 的访问顺序取决于每个节点子节点的遍历顺序。也就是说，一个节点的子节点可以以任意顺序被访问。

我们定义 DFS 访问顺序是一个节点排列序列，表示节点被首次访问时的顺序。

对于每个节点 $v$，请你计算：

• 在所有可能的 DFS 遍历方式中，该节点最早出现在第几个位置；
• 在所有可能的 DFS 遍历方式中，该节点最晚出现在第几个位置。

输入格式

输入包含多个测试用例。

第一行是一个整数 $t$，表示测试用例的数量。

对于每个测试用例：

• 第一行是一个整数 $n$，表示树的节点数量。
• 接下来 $n - 1$ 行，每行两个整数 $x$ 和 $y$，表示节点 $x$ 是节点 $y$ 的父节点。

保证输入构成一棵合法的树，并且根节点是 $1$。

输出格式

对于每个测试用例，输出 $n$ 行，每行两个整数，分别表示该节点在 DFS 序列中出现的最早位置和最晚位置。

样例

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

样例解释

第一个测试用例是一棵链 $1-2-3-4$，DFS 访问顺序唯一，每个节点的最早与最晚位置都等于它的深度。

第二个测试用例中：

• 节点 $1$ 是根，最早和最晚都为 $1$；
• 节点 $2$ 的子树包含 $\{2,3,4\}$ 共 $3$ 个节点，最早为 $2$，最晚为 $5-3+1=3$；
• 节点 $3$、$4$ 是叶子，最早都为 $3$，最晚都为 $5$；
• 节点 $5$ 是叶子，最早为 $2$，最晚为 $5$。

数据范围与约定

对于 $100\%$ 的数据，$1 \le t \le 10^6$，$1 \le n \le 10^5$，且所有测试用例中 $n$ 的总和不超过 $10^6$。所有输入的边都构成一棵以 $1$ 为根的合法树。