D. 可达性与树

每次测试时间限制：2 秒
每次测试内存限制：256 兆字节

题意描述

设 $u$ 和 $v$ 是有向图中两个不同的顶点。若存在从 $u$ 到 $v$ 的一条有向路径，则称有序对 $(u,v)$ 是 好对 (good pair)。

给定一棵包含 $n$ 个顶点和 $n-1$ 条边的 无向树。请判断：是否可能为每条边指定一个方向，使得该有向图中 好对的数量恰好等于 $n$。
如果可能，输出任意一种满足条件的给边定向的方案。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例数量。

每个测试用例：

• 第一行一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 顶点数。
• 接下来 $n-1$ 行，每行两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示树的一条无向边。

数据保证：

• 每个测试用例中的边构成一棵树。
• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例：

• 如果不可能通过定向使好对数量恰好为 $n$，输出 "NO"（大小写不敏感）。
• 否则，输出 "YES"，并在接下来 $n-1$ 行中每行输出两个整数 $u_i, v_i$，表示从 $u_i$ 指向 $v_i$ 的有向边。

边可以按任意顺序输出。如有多个可行答案，输出任意一个。

示例

输入

4
5
1 2
2 4
1 3
3 5
5
1 2
1 3
1 4
4 5
2
2 1
4
3 1
1 2
2 4

输出

YES
1 2
3 1
3 5
4 2
YES
2 1
3 1
4 1
5 4
NO
YES
1 3
2 1
2 4

说明

• 第一个测试用例：示例中的一种定向方式如下图所示。此时恰好有 $5$ 个好对：
  $(3,5),\ (3,1),\ (3,2),\ (1,2),\ (4,2)$。
• 第二个测试用例：示例中的定向方式有 $5$ 个好对：
  $(2,1),\ (3,1),\ (4,1),\ (5,4),\ (5,1)$。
• 第三个测试用例：只有两个顶点，无论边如何定向，都只能产生 $1$ 个好对，不可能得到 $n=2$ 个好对。
• 第四个测试用例：存在可行方案。