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-----

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-----

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.


-----Examples-----
Input
4
3 4
1 4
3 4

Output
YES
1 3
3 2
2 4

Input
3
1 3
1 3

Output
NO

Input
3
1 2
2 3

Output
NO



-----Note-----

Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.  [Image]

Difficulty: interview

Starter code:

Solutions:
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


n = read()
V = []
for _ in range(n-1):
    a, b = readmap()
    V.append(a)
    if b < n:
        print("NO")
        quit()

V.sort()

for i in range(n-1):
    if V[i] <= i:
        print("NO")
        quit()

used = [False] * (n+1)
tree = []
for i in range(n-1):
    v = V[i]
    if not used[v]:
        tree.append(v)
        used[v] = True
    else:
        for j in range(1, n+1):
            if not used[j]:
                tree.append(j)
                used[j] = True
                break
tree.append(n)

print("YES")
for i in range(n-1):
    print(tree[i], tree[i+1])

n = int(input())
V = []
for _ in range(n-1):
    a,b  = map(int, input().split())
    V.append(a)
    if b <n:
        print('NO')
        quit()
V.sort()
for i in range(n-1):
    if V[i]<=i:
        print("NO")
        quit()
used = [False]*(n+1)
tree = []
for i in range(n-1):
    v = V[i]
    if not used[v]:
        tree.append(v)
        used[v]=True
    else:
        for j in range(1,n+1):
            if not used[j]:
                tree.append(j)
                used[j] = True
                break
tree.append(n)
print("YES")
for i in range(n-1):
    print(tree[i],tree[i+1])