Universal Cup Judging System

Universal Cup

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

Lucy 正在為 Xeppelin 競賽準備插圖。對於其中一個問題,她需要畫一張圖。問題在於,要畫出一張好看的圖並不容易。

Lucy 認為,在方格紙上繪製一個含有 $n$ 個頂點和 $m$ 條邊的無向連通圖是最好的選擇。圖的每個頂點都將是網格中的一個格子點 $(x, y)$,每條邊都將是連接點 $(x, y) \leftrightarrow (x + 1, y)$ 或 $(x, y) \leftrightarrow (x, y + 1)$ 的線段(對於某些整數 $x$ 和 $y$)。她只需要將方格圖案的某些部分高亮標示出來,插圖就完成了!

然而,如果繪製的圖能夠保持原圖中的距離,那就更好了。正式地說,考慮二維平面上具有整數座標的點。一個繪製方案是一個由 $n$ 個此類點組成的陣列 $p_1, \dots, p_n$。如果對於所有可能的 $i$ 和 $j$,都有 $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$,則稱該繪製方案是美妙的(nice)。這裡,$\operatorname{dist}(u, v)$ 定義為圖中頂點 $u$ 和 $v$ 之間最短路徑上的邊數,而 $\operatorname{Manhattan}(p_i, p_j)$ 定義為平面上兩個格子點 $p_i$ 和 $p_j$ 之間的曼哈頓距離。

請為給定的圖找到一個美妙的繪製方案,或者指出它不存在。

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

輸入格式

每個測試點包含多組測試資料。第一行包含測試資料的組數 $t$ ($1 \le t \le 50\,000$)。接下來是各組測試資料的描述。

每組測試資料的第一行包含兩個整數 $n$ 和 $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$):圖中的頂點數和邊數。

接下來的 $m$ 行中,每行包含兩個整數 $u$ 和 $v$ ($1 \le u, v \le n$, $u \ne v$):代表圖中由一條邊連接的兩個頂點。保證圖是連通的。

所有測試資料中 $n$ 的總和與 $m$ 的總和均不超過 $500\,000$。

為了便於視覺觀察,每組測試資料之前都有一個空行,可以忽略。

輸出格式

對於每組測試資料,如果不存在美妙的繪製方案,則在單獨一行中輸出 "NO"。

否則,在第一行輸出 "YES"。之後,輸出一個美妙繪製方案的範例。接下來的 $n$ 行中,每行應包含兩個整數 $x_i$ 和 $y_i$:第 $i$ 個點的座標($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$)。如果有多個可能的答案,輸出其中任意一個即可。

範例

範例輸入 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

範例輸出 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

範例輸入 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

範例輸出 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.