Universal Cup Judging System

Universal Cup

حد الوقت: 10.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Lucy forbereder illustrasjonene til Xeppelin Contest. For en av oppgavene ble hun bedt om å tegne en graf. Problemet er at det ikke er lett å tegne en pen graf.

Lucy mener at det beste stedet å tegne en urettet sammenhengende graf med $n$ noder og $m$ kanter er rutepapir. Hver node i grafen vil være et heltallspunkt i rutenettet $(x, y)$, og hver kant vil være en linje som forbinder enten punktene $(x, y) \leftrightarrow (x + 1, y)$ eller $(x, y) \leftrightarrow (x, y + 1)$ for noen heltall $x$ og $y$. Hun kan bare utheve noen deler av rutemønsteret, så er illustrasjonen klar!

Det ville imidlertid vært fint om tegningen bevarte avstandene i grafen. Formelt betrakter vi punkter med heltallskoordinater i et todimensjonalt plan. En tegning er en tabell med $n$ slike punkter $p_1, \dots, p_n$. En tegning er pen hvis $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ for alle mulige $i$ og $j$. Her er $\operatorname{dist}(u, v)$ definert som antall kanter på den korteste stien mellom nodene $u$ og $v$ i grafen, mens $\operatorname{Manhattan}(p_i, p_j)$ er definert som Manhattan-avstanden mellom to heltallspunkter $p_i$ og $p_j$ i planet.

Finn en pen tegning for den gitte grafen, eller oppgi at den ikke finnes.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Inndata

Hver test inneholder flere testtilfeller. Den første linjen inneholder antall testtilfeller $t$ ($1 \le t \le 50\,000$). Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): antall noder og kanter i grafen.

Hver av de neste $m$ linjene inneholder to heltall $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$): de to nodene som er forbundet med en kant i grafen. Grafen er sammenhengende.

Verken summen av $n$ eller summen av $m$ over alle testtilfeller overstiger $500\,000$.

For å gjøre det enklere å lese visuelt, er det en tom linje før hvert testtilfelle. Den kan ignoreres.

Utdata

For hvert testtilfelle, skriv ut "NO" på en enkelt linje hvis det ikke finnes noen pen tegning.

Ellers, skriv ut "YES" på den første linjen. Deretter skriver du ut et eksempel på en pen tegning. Hver av de følgende $n$ linjene skal inneholde to heltall $x_i$ og $y_i$: koordinatene til det $i$-te punktet ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Hvis det finnes flere mulige svar, kan du skrive ut hvilket som helst av dem.

Eksempler

Eksempelinndata 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

Eksempelutdata 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

Eksempelinndata 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

Eksempelutdata 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.