给你一棵树(连通、无向、无环图),其顶点为 $$$n$$$。如果两条边恰好共享一个端点,则它们是相邻的。在一次移动中,您可以删除任意一条边,前提是该边与偶数条剩余边相邻。
删除所有边缘,或确定不可能。如果有多个解决方案,请打印其中一个。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
然后是 $$$n-1$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$u_i$$$,$$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$) 第 $$$i$$$ 条边的端点。保证给定的图是一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果无法去除所有边缘,请打印“NO”。
否则打印“YES”,并在接下来的 $$$n-1$$$ 行中打印删除边缘的可能顺序。对于每条边,以任意顺序打印其端点。
示例
输入 #1
5 2 1 2 3 1 2 2 3 4 1 2 2 3 3 4 5 1 2 2 3 3 4 3 5 7 1 2 1 3 2 4 2 5 3 6 3 7
输出 #1
YES 2 1 NO YES 2 3 3 4 2 1 YES 3 5 2 3 2 1 4 3 NO
注意
测试用例$$$1$$$:可以删除该边,因为它不与任何其他边相邻。
测试用例 $$$2$$$:两条边恰好与一条边相邻,因此不可能删除其中任何一条。所以答案是“不”。
测试用例 $$$3$$$:边 $$$2-3$$$ 与其他两条边相邻。所以是可以去掉的。去除之后,也可以去除剩余的边缘。