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