Hide

Problem J
Jungle Game

Languages en is
/problems/junglegame/file/statement/is/img-0001.jpg
Frumskógur, almenningur

Denise er að hanna frumskógarþemað borðspil. Markmið spilsins er að sérhver leikmaður myndi teymi af tveimur karakterum og takist á við ýmsar áskoranir.

Það eru $N$ ólíkir karakterar númeraðir frá $1$ til $N$. Hver karakter hefur tvo eiginleika $p_i$ og $s_i$ (glúrni og bolmagn). Tölurnar $p_i$ og $s_i$ eru jákvæðar heiltölur sem uppfylla $1 \leq p_i, s_i \leq N$. Áður en leikurinn hefst velur sérhver leikmaður tvo karaktera $i$ og $j$ sem mynda teymi. Velja má sama karakterinn tvisvar. Heildarglúrni og heildarbolmagn teymisins er þá $p_i + p_j$ og $s_i + s_j$.

Í spilinu eru einnig $N$ áskoranir númeraðar frá $1$ til $N$. Sérhver áskorananna hefur einnig tvo eiginleika $P_k$ og $S_k$. Denise hefur þegar hannað allar áskoranirnar og valið tölurnar $P_1, P_2, \dots , P_N$ og $S_1, S_2, \dots , S_N$. Hins vegar gera reglur leiksins ráð fyrir því að ekki sé hægt að mynda teymi sem er með heildarglúrni $P_i$ og heildarbolmagn $S_i$ fyrir einhverja áskorun $i$. Með öðrum orðum ætti

\[ p_i+p_j = P_k \text{ and } s_i+s_j = S_k \]

aldrei að gerast fyrir neina þrennd $i, j, k$ (athugið að $i = j$ er leyfilegt).

Eina sem er eftir er að velja $N$ pör talna $(p_1, s_1), (p_2, s_2) \dots , (p_N, s_N)$ svo að $1 \leq p_i, s_i \leq N$ og vandinn að ofan kemur aldrei upp.

Inntak

Fyrsta lína inntaksins inniheldur heiltöluna $N$ ($1 \leq N \leq 2000$).

Næstu $N$ línur gefa gildi áskorananna $P_i, S_i$ ($1 \leq P_i, S_i \leq 2 \cdot N$).

Úttak

Ef ekki er til nein lausn, prentið “NO”. Prentið annars “YES” og svo $N$ línur, hver þeirra með einu pari heiltalna $p_i, s_i$ ($1 \leq p_i, s_i \leq N$). Þessi pör verða að vera ólík. Með öðrum orðum mega ekki vera til vísar $i \neq j$ svo að $p_i = p_j$ og $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