E. Гарри Поттер и движущиеся лестницы
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Спасаясь от школьного завхоза Филча, Гарри Поттер потерял мантию-невидимку. Отыскать невидимый предмет — задача не из легких. К счастью, у Гарри есть друзья, готовые помочь. Гермиона Грейнджер, которая проштудировала «Мантии-невидимки и все о них», а также шесть томов «Энциклопедии по быстрому поиску кратчайших путей в графах, потоков в сетях, наибольших возрастающих подпоследовательностей и других магических объектов», уже разработала алгоритм поиска мантии-невидимки в сложных динамических системах (каковой и является Хогвартс).

Хогвартс состоит из n этажей, пронумерованных целыми числами от 1 до n. Некоторые пары этажей соединены лестницами. Лестницы могут менять свое положение, перемещая ровно один из концов. Формально: если лестница соединяет этажи a и b, то за одно перемещение она может изменить свое положение так, чтобы соединять этажи a и c или b и c, где c — любой этаж, отличный от a и b. Ни при каких обстоятельствах лестница не может соединять этаж сам с собой. В то же время между парой этажей может быть несколько лестниц.

Изначально Гарри находится на этаже с номером 1. Он не помнит, на каком этаже потерял мантию, и хочет провести поиски на каждом из этажей. Поэтому его цель — посетить каждый из n этажей не менее чем по одному разу. Гарри может посещать этажи в любом порядке и закончить поиски на любом этаже.

В последние годы лестницы перемещаются достаточно редко. Однако Рон и Гермиона готовы наложить заклятие на любую из них, чтобы помочь Гарри в поисках мантии. Чтобы вызывать поменьше подозрений, друзья планируют перемещать лестницы по одной, причем каждую лестницу не более одного раза. В промежутках между перемещением лестниц Гарри сможет передвигаться по этажам, достижимым в данный момент по лестницам, и искать свою мантию-невидимку. Предполагается, что все это время самопроизвольно перемещаться лестницы не будут.

Помогите друзьям разработать план поисков. В случае если вариантов решения несколько, допустим любой корректный вариант (не обязательно оптимальный).

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

В первой строке заданы целые числа n и m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000) — количество этажей и количество лестниц в Хогвартсе соответственно. Следующие m строк содержат пары этажей, соединяемых лестницами в начальный момент времени.

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

В первой строке выведите «YES» (без кавычек), если Гарри сможет обыскать все этажи, и «NO» в противном случае. В случае положительного ответа во второй строке выведите количество лестниц, которые Рон и Гермиона должны будут переместить. Дальнейший вывод должен иметь вид:

перемещения Гарри

перемещение лестницы

перемещения Гарри

перемещение лестницы

...

перемещение лестницы

перемещения Гарри

Каждый блок «перемещения Гарри» должен представлять собой список этажей в порядке их посещения. Суммарное число элементов в списках перемещений Гарри не должно превосходить 106. При выводе каждого списка сначала выводится количество элементов в нем, затем в той же строке — сами элементы через пробел. Первым числом в первом списке должен быть номер 1 (этаж, с которого Гарри начинает поиски). Любой список, кроме первого, может содержать нулевое количество элементов. Обратите внимание, что Гарри может посещать некоторые этажи повторно, но обязательно должен посетить все n этажей хотя бы по одному разу. Два последовательно посещаемых этажа должны быть непосредственно соединены лестницей (в момент перехода между ними). Никакие два этажа, посещенные последовательно, не должны совпадать.

При описании «перемещения лестницы» указывается номер лестницы (лестницы нумеруются целыми числами от 1 до m в порядке их задания во входных данных) и ее новое положение (два номера соединяемых этажей в произвольном порядке).

Одну лестницу можно переместить не более одного раза. Если решений несколько, выведите любое.

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