Lucy er að undirbúa myndskreytingar fyrir Xeppelin-keppnina. Fyrir eitt dæmanna var hún beðin um að teikna net. Vandinn er sá að það er ekki auðvelt að teikna fallegt net.
Lucy telur að besti staðurinn til að teikna óstefnt samanhangandi net með $n$ hnútum og $m$ leggjum sé rúðustrikað blað. Hver hnútur netsins verður heiltölupunktur á grindinni $(x, y)$, og hver leggur verður strik sem tengir annaðhvort punktana $(x, y) \leftrightarrow (x + 1, y)$ eða $(x, y) \leftrightarrow (x, y + 1)$ fyrir einhverjar heiltölur $x$ og $y$. Hún getur einfaldlega litað valda hluta af rúðumynstrinu og þá er myndskreytingin tilbúin!
Hins vegar væri gott ef teikningin varðveitti fjarlægðirnar í netinu. Formlega skoðum við punkta með heiltöluhnit á tvívíðri sléttu. Teikning er fylki af $n$ slíkum punktum $p_1, \dots, p_n$. Teikning er falleg ef $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ fyrir öll möguleg $i$ og $j$. Hér er $\operatorname{dist}(u, v)$ skilgreint sem fjöldi leggja á stysta vegi milli hnútanna $u$ og $v$ í netinu, en $\operatorname{Manhattan}(p_i, p_j)$ er skilgreint sem Manhattan-fjarlægðin milli tveggja heiltölupunkta $p_i$ og $p_j$ á sléttunni.
Finndu fallega teikningu fyrir gefna netið eða tilgreindu að hún sé ekki til.
Inntak
Hvert próf inniheldur mörg prófunartilvik. Fyrsta línan inniheldur fjölda prófunartilvika $t$ ($1 \le t \le 50\,000$). Lýsing á prófunartilvikunum fylgir.
Fyrsta línan í hverju prófunartilviki inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): fjölda hnúta og leggja í netinu.
Hver af næstu $m$ línum inniheldur tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$): hnútana tvo sem tengdir eru með legg í netinu. Netið er samanhangandi.
Bæði summa $n$ og summa $m$ yfir öll prófunartilvik fara ekki yfir $500\,000$.
Til hægðarauka við lestur er auð lína á undan hverju prófunartilviki. Hægt er að hunsa hana.
Úttak
Fyrir hvert prófunartilvik skal prenta "NO" á stakri línu ef engin falleg teikning er til.
Annars skal prenta "YES" á fyrstu línuna. Eftir það skal prenta dæmi um fallega teikningu. Hver af næstu $n$ línum á að innihalda tvær heiltölur $x_i$ og $y_i$: hnit $i$-ta punktsins ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Ef margar lausnir eru mögulegar má prenta hverja sem er þeirra.
Dæmi
Sýnidæmi 1 — Inntak
3 4 4 1 2 2 3 3 4 4 1 5 4 1 2 1 3 1 4 1 5 7 8 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7
Sýnidæmi 1 — Úttak
YES 0 0 1 0 1 1 0 1 YES 3 1 2 1 3 0 4 1 3 2 YES 1 2 2 2 1 3 2 3 3 3 2 4 3 4
Sýnidæmi 2 — Inntak
2 6 6 1 2 2 3 3 4 4 5 5 6 6 1 12 16 1 2 1 3 2 4 3 4 3 5 4 6 5 6 6 7 4 8 7 8 7 9 8 10 9 10 8 11 10 12 11 12
Sýnidæmi 2 — Úttak
NO NO