Universal Cup Judging System

Universal Cup

時間限制: 10.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Lucy đang chuẩn bị các hình minh họa cho kỳ thi Xeppelin. Đối với một trong các bài toán, cô được yêu cầu vẽ một đồ thị. Vấn đề là việc vẽ được một đồ thị đẹp không hề dễ dàng.

Lucy nghĩ rằng nơi tốt nhất để vẽ một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh là giấy kẻ ô vuông. Mỗi đỉnh của đồ thị sẽ là một điểm nguyên trên lưới $(x, y)$, và mỗi cạnh sẽ là một đoạn thẳng nối hai điểm $(x, y) \leftrightarrow (x + 1, y)$ hoặc $(x, y) \leftrightarrow (x, y + 1)$ với các số nguyên $x$ và $y$ nào đó. Cô chỉ cần tô đậm một số phần của mẫu kẻ ô vuông là hình minh họa sẽ hoàn tất!

Tuy nhiên, sẽ thật tuyệt nếu hình vẽ bảo toàn được khoảng cách trong đồ thị. Một cách hình thức, xét các điểm có tọa độ nguyên trên mặt phẳng hai chiều. Một hình vẽ là một mảng gồm $n$ điểm như vậy $p_1, \dots, p_n$. Một hình vẽ được gọi là đẹp nếu $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ với mọi cặp $i$ và $j$ có thể. Ở đây, $\operatorname{dist}(u, v)$ được định nghĩa là số cạnh trên đường đi ngắn nhất giữa hai đỉnh $u$ và $v$ trong đồ thị, còn $\operatorname{Manhattan}(p_i, p_j)$ được định nghĩa là khoảng cách Manhattan giữa hai điểm nguyên $p_i$ và $p_j$ trên mặt phẳng.

Hãy tìm một hình vẽ đẹp cho đồ thị đã cho hoặc chỉ ra rằng nó không tồn tại.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Dữ liệu vào

Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 50\,000$). Mô tả của các bộ dữ liệu tiếp theo như sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): số lượng đỉnh và cạnh trong đồ thị.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$): hai đỉnh được nối với nhau bởi một cạnh của đồ thị. Đồ thị đảm bảo liên thông.

Cả tổng của $n$ và tổng của $m$ trong tất cả các bộ dữ liệu đều không vượt quá $500\,000$.

Để thuận tiện cho việc quan sát, có một dòng trống trước mỗi bộ dữ liệu. Bạn có thể bỏ qua dòng này.

Kết quả

Với mỗi bộ dữ liệu, in ra "NO" trên một dòng nếu không tồn tại hình vẽ đẹp.

Ngược lại, in ra "YES" ở dòng đầu tiên. Sau đó, in ra một ví dụ về hình vẽ đẹp. Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $x_i$ và $y_i$: tọa độ của điểm thứ $i$ ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Nếu có nhiều đáp án thỏa mãn, hãy in ra bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 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

Kết quả 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

Dữ liệu vào 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

Kết quả 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.