Задан неориентированный граф, состоящий из \(n\) вершин и \(m\) ребер.
Напомним, что цикл — это путь, который начинается и заканчивается в одной и той же вершине. Цикл в графе называется простым, если он содержит каждую вершину (за исключением стартовой и конечной) не более одного раза (стартовая и конечная всегда содержится дважды). Заметьте, что петли также считаются простыми циклами.
За один ход Вы можете выбрать любой простой цикл в этом графе и удалить ребра, соответствующие этому циклу (соответствующие вершины остаются в графе). Разрешается удалять петлю или две копии одного ребра (см. тестовые примеры).
Ваша задача — применить некоторую последовательность ходов, чтобы получить граф, в котором нет ребер. Минимизировать количество циклов не обязательно. Если это невозможно, выведите «NO».
Выходные данные
Если невозможно разбить граф на простые циклы, выведите «NO» в первой строке.
Иначе выведите «YES» в первой строке. Во второй строке выведите \(k\) — количество простых циклов в разбиении графа.
В следующих \(k\) строках выведите сами циклы. \(j\)-я строка должна содержать \(j\)-й цикл. Сначала выведите \(c_j\) — количество вершин в \(j\)-м цикле. Затем выведите цикл как последовательность вершин. Все соседние (последовательные) вершины в выведенном пути должны быть соединены ребром, которое не содержится в других циклах.
Примечание
Картинка, соответствующая первому тестовому примеру: 
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|
|
3
|
4 8
1 1
1 2
2 3
3 4
4 1
2 4
1 3
1 3
|
NO
|