Problem J
Jungle Game
Languages
en
is
Denise is designing a rainforest themed board game. The goal of the game is for each player to form a team of two characters and complete various challenges.
There are $N$ different characters numbered from $1$ to $N$. Each character $i$ has two attributes $p_i$ and $s_i$ (problem solving skill and strength). The numbers $p_i$ and $s_i$ are positive integers satisfying $1 \leq p_i, s_i \leq N$. Before the game starts, each player will pick two characters $i$ and $j$ to form a team. It is possible to pick two copies of the same character. The total problem solving skill and strength of the team will be $p_i + p_j$ and $s_i + s_j$ respectively.
In the game there are also $N$ challenge cards numbered from $1$ to $N$. Each of these also has two attributes $P_k$ and $S_k$. Denise has already designed the challenge cards and decided on the values of all numbers $P_1, P_2, \dots , P_N$ and $S_1, S_2, \dots , S_N$. However, the rules of the game assume that it is not possible for a player to form a team whose problem solving skill and strength are both the same as one of the challenge cards. In other words, the situation
\[ p_i+p_j = P_k \text{ and } s_i+s_j = S_k \]should never occur for any triple $i,j,k$ (note that $i$ can be equal to $j$).
The only thing left to do is to decide the $N$ distinct pairs $(p_1, s_1), (p_2, s_2) \dots , (p_N, s_N)$ such that $1 \leq p_i, s_i \leq N$ and the situation above never happens.
Input
The first line contains the integer $N$ ($1 \leq N \leq 2000$).
The following $N$ lines contain the values of the challenge cards $P_i, S_i$ ($1 \leq P_i, S_i \leq 2 \cdot N$).
Output
If there is no solution, print “NO”. Otherwise, print “YES” followed by $N$ lines, each containing a pair of integers $p_i, s_i$ ($1 \leq p_i, s_i \leq N$). These pairs of integers must be distinct. In other words, you may not have two indices $i \neq j$ with $p_i = p_j$ and $s_i = s_j$.
Sample Input 1 | Sample Output 1 |
---|---|
5 5 5 5 6 6 5 6 6 8 8 |
YES 2 2 1 1 1 2 2 1 1 3 |
Sample Input 2 | Sample Output 2 |
---|---|
1 2 2 |
NO |