Universal Cup Judging System

Universal Cup

Süre Sınırı: 10.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Lucy förbereder illustrationerna till Xeppelin Contest. För ett av problemen blev hon ombedd att rita en graf. Problemet är att det inte är lätt att rita en snygg graf.

Lucy tycker att det bästa stället att rita en oriktad sammanhängande graf med $n$ hörn och $m$ kanter är rutat papper. Varje hörn i grafen kommer att vara en heltalspunkt i rutnätet $(x, y)$, och varje kant kommer att vara en linje som förbinder antingen punkterna $(x, y) \leftrightarrow (x + 1, y)$ eller $(x, y) \leftrightarrow (x, y + 1)$ för några heltal $x$ och $y$. Hon kan bara markera vissa delar av rutmönstret, så är illustrationen klar!

Det vore dock trevligt om ritningen bevarade avstånden i grafen. Formellt betraktar vi punkter med heltalskoordinater i ett tvådimensionellt plan. En ritning är en array av $n$ sådana punkter $p_1, \dots, p_n$. En ritning är snygg om $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ för alla möjliga $i$ och $j$. Här definieras $\operatorname{dist}(u, v)$ som antalet kanter på den kortaste vägen mellan hörnen $u$ och $v$ i grafen, medan $\operatorname{Manhattan}(p_i, p_j)$ definieras som Manhattanavståndet mellan två heltalspunkter $p_i$ och $p_j$ i planet.

Hitta en snygg ritning för den givna grafen eller ange att det inte finns någon.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Indata

Varje test innehåller flera testfall. Den första raden innehåller antalet testfall $t$ ($1 \le t \le 50\,000$). Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller två heltal $n$ och $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): antalet hörn och kanter i grafen.

Var och en av de följande $m$ raderna innehåller två heltal $u$ och $v$ ($1 \le u, v \le n$, $u \ne v$): de två hörnen som förbinds av en kant i grafen. Grafen är sammanhängande.

Varken summan av $n$ eller summan av $m$ över alla testfall överstiger $500\,000$.

För att underlätta läsningen finns det en tom rad före varje testfall. Den kan ignoreras.

Utdata

För varje testfall, skriv ut "NO" på en ensam rad om det inte finns någon snygg ritning.

Annars, skriv ut "YES" på den första raden. Skriv därefter ut ett exempel på en snygg ritning. Var och en av de följande $n$ raderna ska innehålla två heltal $x_i$ och $y_i$: koordinaterna för den $i$-te punkten ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Om det finns flera möjliga svar, skriv ut vilket som helst av dem.

Exempel

Exempelindata 1

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

Exempelutdata 1

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

Exempelindata 2

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

Exempelutdata 2

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.