Problem J
Jungle Game
Languages
en
is
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 |