Universal Cup Judging System

Universal Cup

时间限制: 10.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Lucy sta preparando le illustrazioni per lo Xeppelin Contest. Per uno dei problemi le è stato chiesto di disegnare un grafo. Il problema è che non è facile disegnare un bel grafo.

Lucy pensa che il posto migliore per disegnare un grafo connesso non orientato con $n$ vertici e $m$ archi sia la carta a quadretti. Ogni vertice del grafo sarà un punto a coordinate intere della griglia $(x, y)$, e ogni arco sarà un segmento che collega i punti $(x, y) \leftrightarrow (x + 1, y)$ oppure $(x, y) \leftrightarrow (x, y + 1)$ per opportuni interi $x$ e $y$. Le basta evidenziare alcune parti della quadrettatura e l'illustrazione sarà pronta!

Tuttavia, sarebbe bello se il disegno preservasse le distanze nel grafo. Formalmente, consideriamo i punti a coordinate intere su un piano bidimensionale. Un disegno è un array di $n$ tali punti $p_1, \dots, p_n$. Un disegno è bello se $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ per tutti i possibili $i$ e $j$. Qui, $\operatorname{dist}(u, v)$ è definito come il numero di archi sul cammino minimo tra i vertici $u$ e $v$ nel grafo, mentre $\operatorname{Manhattan}(p_i, p_j)$ è definito come la distanza di Manhattan tra due punti interi $p_i$ e $p_j$ sul piano.

Trova un bel disegno per il grafo dato oppure indica che non esiste.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Input

Ogni test contiene più casi di test. La prima riga contiene il numero di casi di test $t$ ($1 \le t \le 50\,000$). Segue la descrizione dei casi di test.

La prima riga di ogni caso di test contiene due interi $n$ e $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): il numero di vertici e di archi nel grafo.

Ciascuna delle successive $m$ righe contiene due interi $u$ e $v$ ($1 \le u, v \le n$, $u \ne v$): i due vertici collegati da un arco del grafo. Il grafo è connesso.

Sia la somma di $n$ sia la somma di $m$ su tutti i casi di test non superano $500\,000$.

Per comodità visiva, c'è una riga vuota prima di ogni caso di test. Può essere ignorata.

Output

Per ogni caso di test, stampa "NO" su una singola riga se non esiste alcun bel disegno.

Altrimenti, stampa "YES" sulla prima riga. Dopodiché, stampa un esempio di bel disegno. Ciascuna delle successive $n$ righe deve contenere due interi $x_i$ e $y_i$: le coordinate dell'$i$-esimo punto ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Se ci sono più risposte possibili, stampane una qualsiasi.

Esempi

Input di esempio 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

Output di esempio 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

Input di esempio 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

Output di esempio 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.