I. Упорядочивание соседей
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для неориентированного графа $$$G$$$ назовем порядком соседей упорядоченный список всех соседей вершины для каждой из вершин $$$G$$$. Рассмотрим некоторый порядок соседей в графе $$$G$$$ и три вершины $$$u$$$, $$$v$$$ и $$$w$$$ такие, что $$$v$$$ является соседом $$$u$$$ и $$$w$$$. Мы будет использовать запись $$$u <_{v} w$$$, если $$$u$$$ стоит после $$$w$$$ в списке соседей вершины $$$v$$$.

Порядок соседей называется хорошим, если для каждого простого цикла $$$v_1, v_2, \ldots, v_c$$$ графа выполняется одно из следующих условий:

  • $$$v_1 <_{v_2} v_3, v_2 <_{v_3} v_4, \ldots, v_{c-2} <_{v_{c-1}} v_c, v_{c-1} <_{v_c} v_1, v_c <_{v_1} v_2$$$,
  • $$$v_1 >_{v_2} v_3, v_2 >_{v_3} v_4, \ldots, v_{c-2} >_{v_{c-1}} v_c, v_{c-1} >_{v_c} v_1, v_c >_{v_1} v_2$$$.

Для заданного графа $$$G$$$ определите, существует ли для него порядок хороших соседей, и постройте его, если он существует.

Входные данные

Входные данные состоят из нескольких наборов входных данных. В первой строке записано единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq m \leq 3 \cdot 10^5$$$), количество вершин и количество ребер графа.

Следующие $$$m$$$ строк содержат по два целых числа $$$u, v$$$ ($$$0 \leq u, v < n$$$), обозначающих, что существует ребро, соединяющее вершины $$$u$$$ и $$$v$$$. Гарантируется, что граф связный и в нем нет петель и кратных ребер.

Сумма $$$n$$$ и сумма $$$m$$$ для всех тестовых случаев не превосходят $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку с «YES», если граф допускает хороший порядок соседей, иначе выведите одну строку с «NO». Вы можете печатать каждую букву в любом регистре (верхнем или нижнем).

Если ответ «YES», дополнительно выведите $$$n$$$ строк, описывающих порядок хороших соседей. В $$$i$$$-й строке выведите соседей вершины $$$i$$$ по порядку.

Пример
Входные данные
3
5 6
0 1
0 2
1 2
2 3
3 4
4 1
2 1
0 1
6 10
0 1
2 0
0 3
0 4
1 2
1 4
2 3
2 5
3 5
4 5
Выходные данные
YES
1 2 
4 2 0 
0 1 3 
2 4 
3 1 
YES
1 
0 
NO