题目描述

黑猫老师有一棵以 $1$ 为根的树，这棵树有 $n$ 个节点。这 $n$ 个节点的编号从 $1$ 到 $n$。

现在他想从根节点开始进行深度优先搜索。他想知道对于每个节点 $v$，它在深度优先搜索顺序中出现的最早和最晚位置。

深度优先搜索顺序 是指在深度优先搜索过程中访问节点的顺序。一个节点出现在这个顺序中的第 $j$ 个位置（$1 \le j \le n$）意味着它是在 $j-1$ 个其他节点之后被访问的。

由于一个节点的子节点可以以任意顺序进行迭代，因此存在多种可能的深度优先顺序。黑猫老师想知道对于每个节点 $v$，最早和最晚被访问的顺序是多少。

输入格式

第一行包含一个整数 $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