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 prépare les illustrations pour le concours Xeppelin. Pour l'un des problèmes, on lui a demandé de dessiner un graphe. Le souci, c'est qu'il n'est pas facile de dessiner un joli graphe.

Lucy pense que le meilleur support pour dessiner un graphe connexe non orienté à $n$ sommets et $m$ arêtes est du papier quadrillé. Chaque sommet du graphe sera un point à coordonnées entières de la grille $(x, y)$, et chaque arête sera un segment reliant soit les points $(x, y) \leftrightarrow (x + 1, y)$, soit $(x, y) \leftrightarrow (x, y + 1)$ pour certains entiers $x$ et $y$. Il lui suffit de surligner certaines parties du quadrillage et l'illustration sera prête !

Cependant, ce serait bien que le dessin préserve les distances dans le graphe. Formellement, considérons des points à coordonnées entières dans un plan bidimensionnel. Un dessin est un tableau de $n$ tels points $p_1, \dots, p_n$. Un dessin est joli si $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ pour tous les $i$ et $j$ possibles. Ici, $\operatorname{dist}(u, v)$ est défini comme le nombre d'arêtes sur le plus court chemin entre les sommets $u$ et $v$ dans le graphe, tandis que $\operatorname{Manhattan}(p_i, p_j)$ est défini comme la distance de Manhattan entre deux points entiers $p_i$ et $p_j$ du plan.

Trouvez un joli dessin pour le graphe donné ou indiquez qu'il n'en existe pas.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Entrée

Chaque test contient plusieurs cas de test. La première ligne contient le nombre de cas de test $t$ ($1 \le t \le 50\,000$). La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $n$ et $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$) : le nombre de sommets et d'arêtes dans le graphe.

Chacune des $m$ lignes suivantes contient deux entiers $u$ et $v$ ($1 \le u, v \le n$, $u \ne v$) : les deux sommets reliés par une arête du graphe. Le graphe est connexe.

La somme des $n$ ainsi que la somme des $m$ sur l'ensemble des cas de test ne dépassent pas $500\,000$.

Pour le confort visuel, il y a une ligne vide avant chaque cas de test. Elle peut être ignorée.

Sortie

Pour chaque cas de test, affichez "NO" sur une seule ligne s'il n'existe aucun joli dessin.

Sinon, affichez "YES" sur la première ligne. Ensuite, affichez un exemple de joli dessin. Chacune des $n$ lignes suivantes doit contenir deux entiers $x_i$ et $y_i$ : les coordonnées du $i$-ème point ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). S'il existe plusieurs réponses possibles, affichez-en une quelconque.

Exemples

Entrée d'exemple 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

Sortie d'exemple 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

Entrée d'exemple 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

Sortie d'exemple 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.