Люси готовит иллюстрации для соревнования 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$ на плоскости.
Найдите красивый рисунок для заданного графа или укажите, что его не существует.
Входные данные
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $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