Universal Cup Judging System

Universal Cup

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

Lucy está preparando las ilustraciones para el concurso Xeppelin. Para uno de los problemas, le pidieron que dibujara un grafo. El inconveniente es que no resulta fácil dibujar un grafo bonito.

Lucy piensa que el mejor lugar para dibujar un grafo conexo no dirigido con $n$ vértices y $m$ aristas es el papel cuadriculado. Cada vértice del grafo será un punto entero de la cuadrícula $(x, y)$, y cada arista será un segmento que conecte los puntos $(x, y) \leftrightarrow (x + 1, y)$ o $(x, y) \leftrightarrow (x, y + 1)$ para algunos enteros $x$ e $y$. ¡Solo tiene que resaltar algunas partes del patrón cuadriculado y la ilustración estará lista!

Sin embargo, sería bueno que el dibujo preservara las distancias en el grafo. Formalmente, consideremos puntos con coordenadas enteras en un plano bidimensional. Un dibujo es un arreglo de $n$ puntos de este tipo $p_1, \dots, p_n$. Un dibujo es bonito si $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ para todos los $i$ y $j$ posibles. Aquí, $\operatorname{dist}(u, v)$ se define como el número de aristas en el camino más corto entre los vértices $u$ y $v$ en el grafo, mientras que $\operatorname{Manhattan}(p_i, p_j)$ se define como la distancia de Manhattan entre dos puntos enteros $p_i$ y $p_j$ en el plano.

Encuentra un dibujo bonito para el grafo dado o indica que no existe.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 50\,000$). A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): el número de vértices y aristas en el grafo.

Cada una de las siguientes $m$ líneas contiene dos enteros $u$ y $v$ ($1 \le u, v \le n$, $u \ne v$): los dos vértices conectados por una arista del grafo. El grafo es conexo.

Tanto la suma de $n$ como la suma de $m$ en todos los casos de prueba no superan $500\,000$.

Para facilitar la lectura visual, hay una línea vacía antes de cada caso de prueba. Puede ignorarse.

Salida

Para cada caso de prueba, imprime "NO" en una sola línea si no existe ningún dibujo bonito.

En caso contrario, imprime "YES" en la primera línea. Después de eso, imprime un ejemplo de un dibujo bonito. Cada una de las siguientes $n$ líneas debe contener dos enteros $x_i$ e $y_i$: las coordenadas del $i$-ésimo punto ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Si hay varias respuestas posibles, imprime cualquiera de ellas.

Ejemplos

Entrada de ejemplo 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

Salida de ejemplo 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

Entrada de ejemplo 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

Salida de ejemplo 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.