DFS Order

题目描述

有一棵以 1 为根的树，共 n 个结点，编号 1..n。 我们从根结点开始做先序 DFS（到一个点就立刻把它记进序列，然后依次递归访问它的每个儿子）。儿子们的访问顺序可以任意打乱，因此可能得到很多种不同的 DFS 访问序列。

对树上的每个结点 v，我们关心它在这些所有可能的 DFS 序列中出现的最早位置和最晚位置（位置从 1 到 n，位置 j 表示前面有 j-1 个点先被访问）。

伪代码（dfs_order 是访问顺序）：

let dfs_order be an empty list

def dfs(x):
    append x to the end of dfs_order
    for (each son y of x in ANY 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 为根的树）。

保证所有测试用例的 n 之和不超过 \(10^6\)。

输出格式

对每组数据输出 n 行。 第 i 行输出两个整数：结点 i 在 DFS 序列中的最早位置与最晚位置。

输入输出样例 #1

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