Universal Cup Judging System

Universal Cup

Süre Sınırı: 10.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Люси готовит иллюстрации для соревнования 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.