G. Разбиение графа
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер.

Напомним, что цикл — это путь, который начинается и заканчивается в одной и той же вершине. Цикл в графе называется простым, если он содержит каждую вершину (за исключением стартовой и конечной) не более одного раза (стартовая и конечная всегда содержится дважды). Заметьте, что петли также считаются простыми циклами.

За один ход Вы можете выбрать любой простой цикл в этом графе и удалить ребра, соответствующие этому циклу (соответствующие вершины остаются в графе). Разрешается удалять петлю или две копии одного ребра (см. тестовые примеры).

Ваша задача — применить некоторую последовательность ходов, чтобы получить граф, в котором нет ребер. Минимизировать количество циклов не обязательно. Если это невозможно, выведите «NO».

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

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

Следующие $$$m$$$ строк содержат ребра графа. $$$i$$$-я строка содержит $$$i$$$-е ребро $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$), где $$$x_i$$$ и $$$y_i$$$ — вершины, соединенные $$$i$$$-м ребром. Граф может содержать петли и кратные ребра.

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

Если невозможно разбить граф на простые циклы, выведите «NO» в первой строке.

Иначе выведите «YES» в первой строке. Во второй строке выведите $$$k$$$ — количество простых циклов в разбиении графа.

В следующих $$$k$$$ строках выведите сами циклы. $$$j$$$-я строка должна содержать $$$j$$$-й цикл. Сначала выведите $$$c_j$$$ — количество вершин в $$$j$$$-м цикле. Затем выведите цикл как последовательность вершин. Все соседние (последовательные) вершины в выведенном пути должны быть соединены ребром, которое не содержится в других циклах.

Примеры
Входные данные
6 9
1 2
2 3
1 3
2 4
2 5
4 5
3 5
3 6
5 6
Выходные данные
YES
3
4 2 5 4 2 
4 3 6 5 3 
4 1 3 2 1
Входные данные
4 7
1 1
1 2
2 3
3 4
4 1
1 3
1 3
Выходные данные
YES
3
2 1 1 
5 1 4 3 2 1 
3 1 3 1
Входные данные
4 8
1 1
1 2
2 3
3 4
4 1
2 4
1 3
1 3
Выходные данные
NO
Примечание

Картинка, соответствующая первому тестовому примеру: