Universal Cup Judging System

Universal Cup

Limite de temps : 10.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

לוסי מכינה את האיורים לתחרות Xeppelin. עבור אחת הבעיות, היא התבקשה לצייר גרף. הבעיה היא שלא קל לצייר גרף יפה.

לוסי חושבת שהמקום הטוב ביותר לצייר בו גרף קשיר לא מכוון עם $n$ צמתים ו-$m$ קשתות הוא דף משובץ. כל צומת בגרף יהיה נקודה שלמה ברשת $(x, y)$, וכל קשת תהיה קו המחבר בין הנקודות $(x, y) \leftrightarrow (x + 1, y)$ או $(x, y) \leftrightarrow (x, y + 1)$ עבור מספרים שלמים כלשהם $x$ ו-$y$. היא יכולה פשוט להדגיש חלקים מהדפוס המשובץ, והאיור יהיה מוכן!

עם זאת, יהיה נחמד אם הציור ישמור על המרחקים בגרף. באופן פורמלי, נתבונן בנקודות בעלות קואורדינטות שלמות במישור דו-ממדי. ציור הוא מערך של $n$ נקודות כאלה $p_1, \dots, p_n$. ציור נקרא יפה אם $\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.