Universal Cup Judging System

Universal Cup

Límite de tiempo: 10.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

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.