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