Universal Cup Judging System

Universal Cup

Time Limit: 10.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.