← 返回题目列表

Codeforces · 2112/D

D. 可达性和树

中文机器翻译题面 查看原题

令 $$$u$$$ 和 $$$v$$$ 为有向图中两个不同的顶点。我们将有序对称为 $$$(u, v)$$$ 好 如果沿着图的边存在从顶点 $$$u$$$ 到顶点 $$$v$$$ 的路径。

给你一棵无向树,有 $$$n$$$ 个顶点和 $$$n - 1$$$ 个边。确定是否可以为这棵树的每条边分配一个方向,使得其中的好对的数量为 正是 $$$n$$$。如果可能的话,打印任何方式来引导边缘,从而产生精确的 $$$n$$$ 好对。

第一个测试用例的树的一个可能的定向版本。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行描述边缘。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) - 由第 $$$i$$$ 条边连接的顶点。

保证每个测试用例中的边形成无向树,并且所有测试用例的 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印“NO“(不区分大小写)如果不可能引导树的所有边并准确获得 $$$n$$$ 好的顶点对。

否则,打印“是"(不区分大小写),然后打印 $$$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)$$$。

在第三个测试用例中,只有两对有向顶点,但对于任何方向的边,只有一对就可以了。