Lucy förbereder illustrationerna till Xeppelin Contest. För ett av problemen blev hon ombedd att rita en graf. Problemet är att det inte är lätt att rita en snygg graf.
Lucy tycker att det bästa stället att rita en oriktad sammanhängande graf med $n$ hörn och $m$ kanter är rutat papper. Varje hörn i grafen kommer att vara en heltalspunkt i rutnätet $(x, y)$, och varje kant kommer att vara en linje som förbinder antingen punkterna $(x, y) \leftrightarrow (x + 1, y)$ eller $(x, y) \leftrightarrow (x, y + 1)$ för några heltal $x$ och $y$. Hon kan bara markera vissa delar av rutmönstret, så är illustrationen klar!
Det vore dock trevligt om ritningen bevarade avstånden i grafen. Formellt betraktar vi punkter med heltalskoordinater i ett tvådimensionellt plan. En ritning är en array av $n$ sådana punkter $p_1, \dots, p_n$. En ritning är snygg om $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ för alla möjliga $i$ och $j$. Här definieras $\operatorname{dist}(u, v)$ som antalet kanter på den kortaste vägen mellan hörnen $u$ och $v$ i grafen, medan $\operatorname{Manhattan}(p_i, p_j)$ definieras som Manhattanavståndet mellan två heltalspunkter $p_i$ och $p_j$ i planet.
Hitta en snygg ritning för den givna grafen eller ange att det inte finns någon.
Indata
Varje test innehåller flera testfall. Den första raden innehåller antalet testfall $t$ ($1 \le t \le 50\,000$). Beskrivningen av testfallen följer.
Den första raden i varje testfall innehåller två heltal $n$ och $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): antalet hörn och kanter i grafen.
Var och en av de följande $m$ raderna innehåller två heltal $u$ och $v$ ($1 \le u, v \le n$, $u \ne v$): de två hörnen som förbinds av en kant i grafen. Grafen är sammanhängande.
Varken summan av $n$ eller summan av $m$ över alla testfall överstiger $500\,000$.
För att underlätta läsningen finns det en tom rad före varje testfall. Den kan ignoreras.
Utdata
För varje testfall, skriv ut "NO" på en ensam rad om det inte finns någon snygg ritning.
Annars, skriv ut "YES" på den första raden. Skriv därefter ut ett exempel på en snygg ritning. Var och en av de följande $n$ raderna ska innehålla två heltal $x_i$ och $y_i$: koordinaterna för den $i$-te punkten ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Om det finns flera möjliga svar, skriv ut vilket som helst av dem.
Exempel
Exempelindata 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
Exempelutdata 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
Exempelindata 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
Exempelutdata 2
NO NO