令 $$$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$$$ 的边。
边缘可以按任何顺序打印。如果有多个答案,则输出任意一个。
示例
输入复制
451 22 41 33 551 21 31 44 522 143 11 22 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)$$$。
在第三个测试用例中,只有两对有向顶点,但对于任何方向的边,只有一对就可以了。