Lucy forbereder illustrasjonene til Xeppelin Contest. For en av oppgavene ble hun bedt om å tegne en graf. Problemet er at det ikke er lett å tegne en pen graf.
Lucy mener at det beste stedet å tegne en urettet sammenhengende graf med $n$ noder og $m$ kanter er rutepapir. Hver node i grafen vil være et heltallspunkt i rutenettet $(x, y)$, og hver kant vil være en linje som forbinder enten punktene $(x, y) \leftrightarrow (x + 1, y)$ eller $(x, y) \leftrightarrow (x, y + 1)$ for noen heltall $x$ og $y$. Hun kan bare utheve noen deler av rutemønsteret, så er illustrasjonen klar!
Det ville imidlertid vært fint om tegningen bevarte avstandene i grafen. Formelt betrakter vi punkter med heltallskoordinater i et todimensjonalt plan. En tegning er en tabell med $n$ slike punkter $p_1, \dots, p_n$. En tegning er pen hvis $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ for alle mulige $i$ og $j$. Her er $\operatorname{dist}(u, v)$ definert som antall kanter på den korteste stien mellom nodene $u$ og $v$ i grafen, mens $\operatorname{Manhattan}(p_i, p_j)$ er definert som Manhattan-avstanden mellom to heltallspunkter $p_i$ og $p_j$ i planet.
Finn en pen tegning for den gitte grafen, eller oppgi at den ikke finnes.
Inndata
Hver test inneholder flere testtilfeller. Den første linjen inneholder antall testtilfeller $t$ ($1 \le t \le 50\,000$). Beskrivelsen av testtilfellene følger.
Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): antall noder og kanter i grafen.
Hver av de neste $m$ linjene inneholder to heltall $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$): de to nodene som er forbundet med en kant i grafen. Grafen er sammenhengende.
Verken summen av $n$ eller summen av $m$ over alle testtilfeller overstiger $500\,000$.
For å gjøre det enklere å lese visuelt, er det en tom linje før hvert testtilfelle. Den kan ignoreres.
Utdata
For hvert testtilfelle, skriv ut "NO" på en enkelt linje hvis det ikke finnes noen pen tegning.
Ellers, skriv ut "YES" på den første linjen. Deretter skriver du ut et eksempel på en pen tegning. Hver av de følgende $n$ linjene skal inneholde to heltall $x_i$ og $y_i$: koordinatene til det $i$-te punktet ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Hvis det finnes flere mulige svar, kan du skrive ut hvilket som helst av dem.
Eksempler
Eksempelinndata 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
Eksempelutdata 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
Eksempelinndata 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
Eksempelutdata 2
NO NO