Prof. Pang 有一棵以 1 为根的有根树，共有 $n$ 个节点。这些节点编号为 1 到 $n$。

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

以下是该有根树深度优先搜索的伪代码。执行完毕后，dfs_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)

输入格式

第一行包含一个整数 $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$ 在深度优先搜索序列中可能出现的最小位置和最大位置。

样例

输入 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