← 返回题目列表

Codeforces · 1667/D

D. 边缘消除

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

给你一棵树(连通、无向、无环图),其顶点为 $$$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$$$ 与其他两条边相邻。所以是可以去掉的。去除之后,也可以去除剩余的边缘。