Universal Cup Judging System

Universal Cup

时间限制: 10.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

Lucy sedang menyiapkan ilustrasi untuk Kontes Xeppelin. Untuk salah satu soal, ia diminta menggambar sebuah graf. Masalahnya, tidak mudah untuk menggambar graf yang bagus.

Lucy berpikir bahwa tempat terbaik untuk menggambar graf terhubung tak berarah dengan $n$ simpul dan $m$ sisi adalah kertas berpetak. Setiap simpul dari graf akan menjadi titik bulat pada kisi $(x, y)$, dan setiap sisi akan menjadi garis yang menghubungkan titik $(x, y) \leftrightarrow (x + 1, y)$ atau $(x, y) \leftrightarrow (x, y + 1)$ untuk suatu bilangan bulat $x$ dan $y$. Ia cukup menyorot beberapa bagian dari pola berpetak tersebut, dan ilustrasinya akan siap!

Namun, akan lebih baik jika gambar tersebut mempertahankan jarak di dalam graf. Secara formal, tinjau titik-titik dengan koordinat bulat pada bidang dua dimensi. Sebuah gambar adalah sebuah larik yang terdiri atas $n$ titik demikian $p_1, \dots, p_n$. Sebuah gambar dikatakan bagus jika $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ untuk semua $i$ dan $j$ yang mungkin. Di sini, $\operatorname{dist}(u, v)$ didefinisikan sebagai banyaknya sisi pada lintasan terpendek antara simpul $u$ dan $v$ di dalam graf, sedangkan $\operatorname{Manhattan}(p_i, p_j)$ didefinisikan sebagai jarak Manhattan antara dua titik bulat $p_i$ dan $p_j$ pada bidang.

Temukan sebuah gambar yang bagus untuk graf yang diberikan atau nyatakan bahwa gambar demikian tidak ada.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Masukan

Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $t$ ($1 \le t \le 50\,000$). Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): banyaknya simpul dan sisi di dalam graf.

Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u \ne v$): dua simpul yang dihubungkan oleh sebuah sisi pada graf. Graf dijamin terhubung.

Baik jumlah nilai $n$ maupun jumlah nilai $m$ di seluruh kasus uji tidak melebihi $500\,000$.

Untuk kenyamanan visual, terdapat satu baris kosong sebelum setiap kasus uji. Baris kosong ini dapat diabaikan.

Keluaran

Untuk setiap kasus uji, cetak "NO" pada satu baris jika tidak ada gambar yang bagus.

Sebaliknya, cetak "YES" pada baris pertama. Setelah itu, cetak sebuah contoh gambar yang bagus. Masing-masing dari $n$ baris berikutnya harus berisi dua bilangan bulat $x_i$ dan $y_i$: koordinat dari titik ke-$i$ ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Jika terdapat beberapa kemungkinan jawaban, cetak salah satu di antaranya.

Contoh

Contoh Masukan 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

Contoh Keluaran 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

Contoh Masukan 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

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