Universal Cup Judging System

Universal Cup

実行時間制限: 10.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

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.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.