Tree Reconstruction
Contest: Codeforces Round 509 (Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, data structures, graphs, greedy

Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from $$$1$$$ to $$$n$$$. For every edge $$$e$$$ of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge $$$e$$$ (and only this edge) is erased from the tree.

Monocarp has given you a list of $$$n - 1$$$ pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 1\,000$$$) — the number of vertices in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ each ($$$1 \le a_i < b_i \le n$$$) — the maximal indices of vertices in the components formed if the $$$i$$$-th edge is removed.

Output format:
If there is no such tree that can produce the given list of pairs, print "NO" (without quotes).

Otherwise print "YES" (without quotes) in the first line and the edges of the tree in the next $$$n - 1$$$ lines. Each of the last $$$n - 1$$$ lines should contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — vertices connected by an edge.

Note: The numeration of edges doesn't matter for this task. Your solution will be considered correct if your tree produces the same pairs as given in the input file (possibly reordered). That means that you can print the edges of the tree you reconstructed in any order.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.

Example input:
4
3 4
1 4
3 4

Example output:
YES
1 3
3 2
2 4

Example input:
3
1 3
1 3

Example output:
NO

Editorial:
First of all, if there exists some $$$b_i < n$$$, then the answer is clearly NO. Then let's consider that every $$$b_i = n$$$ and analyze only the values of $$$a_i$$$ (and furthermore, let's sort all values of $$$a_i$$$ beforehand).
Suppose that we have constructed a tree satisfying all the requirements and rooted it at vertex $$$n$$$. Then for any $$$k$$$ such that $$$1 \le k \le n - 1$$$ there exist no more than $$$k$$$ subtrees containing only vertices with indices not exceeding $$$k$$$ (because there are no more than $$$k$$$ vertices that can be the roots of such subtrees). So, if for some constant $$$k$$$ the number of $$$a_i \le k$$$ is greater than $$$k$$$, then the answer is NO since it would imply that there are more than $$$k$$$ subtrees containing only values not greater then $$$k$$$.
Now we consider only the case such that for every $$$k \in [1, n - 1]$$$ the number of $$$i$$$ such that $$$a_i \le k$$$ is not greater than $$$k$$$. In this case the answer is YES; let's prove it with an algorithm that constructs a tree meeting the constraints.
Actually, we can always build a bamboo (a tree where no vertex has degree greater than $$$2$$$, or simply a path) according to these constraints. Let's put vertex $$$n$$$ at one of the ends of the bamboo and start building a bamboo from the other end. It's obvious that if we make some vertex $$$x$$$ a leaf, then the array $$$a$$$ will contain only values not less than $$$x$$$. So, if we consider values of $$$a_i$$$ to be sorted, then the leaf has index $$$a_1$$$.
Then let's repeat the following process for every $$$i \in [2, n - 1]$$$:
• if $$$a_i > a_{i - 1}$$$, then let's use the vertex with index $$$a_i$$$ as the parent of the previous vertex;
• otherwise, let's find any index $$$j$$$ such that $$$j < a_i$$$ and index $$$j$$$ is not used yet, and use vertex with index $$$j$$$ as the parent of the previous vertex (there will be at least one such vertex since for every $$$k \in [1, n - 1]$$$ the number of $$$i$$$ such that $$$a_i \le k$$$ is not greater than $$$k$$$).
It's easy to prove that the bamboo we construct in such a way meets the constraints given in the statement.