快来看看这题怎么做啊

DFS序

题目描述

给你一棵

n

个节点的以 1 号节点为根的树，节点的编号为 1 到

n

我们想从根节点出发，深度优先遍历（DFS）这棵树。我们想知道对于任意节点

v

, 它最前和最后分别可以出现在 DFS 序的哪个位置。DFS 序指的是在 DFS 过程中访问节点的顺序。一个节点出现在 DFS 序的第

j

个位置意味着在访问这个节点前我们恰好访问了

j-1

个其他节点。

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

CPP

初始 dfs_order 为空

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

dfs(root)

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

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

对于每组数据，输出对应的 ? 行，第 ? 行两个整数表示 ? 号节点最前和最后分别可以出现在 DFS 序的哪个位置。

CPP

CPP

对于 30% 的数据，保证

1 \le T,n \le 10

。

对于 100% 的数据，保证

1 \le n \le 10^5

1 \le x,y \le n

，所有数据的

n

相加不超过

10^6

。