T589707 「2025 YAC Round 7」东之国的不眠夜

 图片来源：[pixiv_id=57366270](https://www.pixiv.net/artworks/57366270)

东之国有 $n$ 个城市 和 $n - 1$ 条双向道路，城市编号从 $1\sim n$，任意城市之间可以通过道路互相到达。 文文从城市 $1$ 开始旅行，她决定用 **[深度优先搜索](https://oi-wiki.org/graph/dfs/)** 的方式访问所有 $n$ 个城市。 文文想要知道：对于每个城市 $i$（$1 \le i \le n$），城市 $i$ **最早** 会在 **第几个** 被访问到，以及 **最晚** 会在 **第几个** 被访问到。

**本题测试点有多组数据** 第一行输入一个整数 $T$（$1 \le T \le 10^6$），表示数据组数。 **对于每组数据：** 第一行输入一个整数 $n$（$1\le n \le 10^5$），表示城市数量。 接下来 $n - 1$ 行每行输入两个整数 $u, v$（$1 \le u, v\le n, u\neq v$），表示城市 $u$ 和 $v$ 之间有一条双向道路。 输入数据 **保证 $\sum n \le 10^6$**。

**对于每组数据：** 输出 $n$ 行。第 $i$ 行包含两个整数 $t_{min},t_{max}$，分别表示城市 $i$ **最早** 会在 **第几个** 被访问到，以及 **最晚** 会在 **第几个** 被访问到。