← 返回题目列表

Codeforces · 1041/E

E. 树重建

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

Monocarp 绘制了一棵树(无向连通无环图),然后给每个顶点一个索引。所有索引都是从 $$$1$$$ 到 $$$n$$$ 的不同数字。对于该树的每条边 $$$e$$$,Monocarp 写入了两个数字:如果从树中删除边 $$$e$$$(并且仅此边),则形成的两个组件的顶点的最大索引。

Monocarp 为您提供了 $$$n - 1$$$ 数字对的列表。他希望您提供一个树的示例,如果该树存在,它将生成上述列表。如果这样的树不存在,请说明。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1\,000$$$) — 树中的顶点数。

接下来的 $$$n-1$$$ 行均包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i < b_i \le n$$$) - 如果删除第 $$$i$$$ 条边,则形成的组件中顶点的最大索引。

输出

如果没有这样的树可以生成给定的对列表,则打印“NO”(不带引号)。

否则在第一行中打印“YES”(不带引号),并在接下来的 $$$n - 1$$$ 行中打印树的边缘。最后 $$$n - 1$$$ 行中的每一行都应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — 由边连接的顶点。

注意:边的数量对于此任务并不重要。如果您的树生成与输入文件中给出的相同的对(可能已重新排序),则您的解决方案将被认为是正确的。这意味着您可以按任何顺序打印重建的树的边缘。

示例

输入 #1

4
3 4
1 4
3 4

输出 #1

YES
1 3
3 2
2 4

输入 #2

3
1 3
1 3

输出 #2

NO

输入 #3

3
1 2
2 3

输出 #3

NO

注意

第一个示例中可能的树。虚线显示您需要删除以获得合适的对的边缘。