快来看看这题怎么做啊

DFS序

题目描述

给你一棵 $n$ 个节点的以 1 号节点为根的树，节点的编号为 1 到 $n$.

我们想从根节点出发，深度优先遍历（DFS）这棵树。 我们想知道对于任意节点 $v$, 它最前和最后分别可以出现在 DFS 序的哪个位置。DFS 序指的是在 DFS 过程中访问节点的顺序。一个节点出现在 DFS 序的第 $j$ 个位置意味着在访问这个节点前我们恰好访问了 $j-1$ 个其他节点。

下面是有根树 DFS 的伪代码，程序执行完毕后, dfs_order 记录了这棵树的 DFS 序。

初始 dfs_order 为空

def dfs(vertex x):
    把 x 加到 dfs_order 的末尾
    for (x 的每个子节点 y): //注意，我们可以按照任意顺序枚举子节点
        dfs(y)

dfs(root)

输入格式

第一行输入一个正整数 ? 表示数据组数。

对于每组数据，第一行一个正整数 ? 表示节点数。接下来 ?−1 行，每行两个正整数 ?,?，表示 ? 号节点是 ? 号节点的父亲节点。 数据保证读入的是一棵以 1 号节点为根的树。

输出格式

对于每组数据，输出对应的 ? 行，第 ? 行两个整数表示 ? 号节点最前和最后分别可以出现在 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

数据规模

对于 30% 的数据，保证 $1 \le T,n \le 10$。

对于 100% 的数据，保证 $1 \le n \le 10^5$, $1 \le x,y \le n$，所有数据的 $n$ 相加不超过 $10^6$。