Люсі готує ілюстрації для змагання 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