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
注意
第一个示例中可能的树。虚线显示您需要删除以获得合适的对的边缘。