Universal Cup Judging System

Universal Cup

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

Люсі готує ілюстрації для змагання Xeppelin Contest. Для однієї із задач її попросили намалювати граф. Проблема в тому, що намалювати гарний граф непросто.

Люсі вважає, що найкраще місце для малювання неорієнтованого зв'язного графа з $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.