Lucy valmistelee kuvituksia Xeppelin Contest -kilpailuun. Yhteen tehtävistä häntä pyydettiin piirtämään verkko. Ongelmana on, ettei hienon verkon piirtäminen ole helppoa.
Lucyn mielestä paras paikka piirtää suuntaamaton yhtenäinen verkko, jossa on $n$ solmua ja $m$ kaarta, on ruutupaperi. Verkon jokainen solmu on ruudukon kokonaislukupiste $(x, y)$, ja jokainen kaari on jana, joka yhdistää joko pisteet $(x, y) \leftrightarrow (x + 1, y)$ tai $(x, y) \leftrightarrow (x, y + 1)$ joillekin kokonaisluvuille $x$ ja $y$. Hän voi vain korostaa osan ruutukuviosta, ja kuvitus on valmis!
Olisi kuitenkin hienoa, jos piirros säilyttäisi verkon etäisyydet. Muodollisesti tarkastellaan kaksiulotteisen tason pisteitä, joiden koordinaatit ovat kokonaislukuja. Piirros on $n$ tällaisen pisteen taulukko $p_1, \dots, p_n$. Piirros on hieno, jos $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ kaikilla mahdollisilla $i$ ja $j$. Tässä $\operatorname{dist}(u, v)$ määritellään kaarien lukumääränä verkon solmujen $u$ ja $v$ välisellä lyhimmällä polulla, kun taas $\operatorname{Manhattan}(p_i, p_j)$ määritellään tason kahden kokonaislukupisteen $p_i$ ja $p_j$ välisenä Manhattan-etäisyytenä.
Etsi annetulle verkolle hieno piirros tai ilmoita, ettei sellaista ole olemassa.
Syöte
Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää testitapausten lukumäärän $t$ ($1 \le t \le 50\,000$). Seuraavaksi esitetään testitapausten kuvaukset.
Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): verkon solmujen ja kaarien lukumäärän.
Jokainen seuraavista $m$ rivistä sisältää kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u \ne v$): kaksi verkon kaarella yhdistettyä solmua. Verkko on yhtenäinen.
Sekä lukujen $n$ summa että lukujen $m$ summa yli kaikkien testitapausten ovat korkeintaan $500\,000$.
Hahmottamisen helpottamiseksi jokaisen testitapauksen edellä on tyhjä rivi. Sen voi jättää huomiotta.
Tuloste
Tulosta jokaista testitapausta kohden omalle rivilleen "NO", jos hienoa piirrosta ei ole olemassa.
Muussa tapauksessa tulosta ensimmäiselle riville "YES". Tulosta sen jälkeen esimerkki hienosta piirroksesta. Jokaisella seuraavista $n$ rivistä tulee olla kaksi kokonaislukua $x_i$ ja $y_i$: $i$:nnen pisteen koordinaatit ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Jos mahdollisia vastauksia on useita, tulosta mikä tahansa niistä.
Esimerkit
Esimerkkisyöte 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
Esimerkkituloste 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
Esimerkkisyöte 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
Esimerkkituloste 2
NO NO