32558번 - Jungle Game 스페셜 저지다국어

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.

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$).

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