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$ การวาดจะเรียกว่า สวยงาม (nice) หาก $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ สำหรับทุกค่า $i$ และ $j$ ที่เป็นไปได้ ในที่นี้ $\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.