Агент Джонни Инглиш учился в школе разведки. Однажды в качестве задания ему было предложено заминировать некоторые города, чтобы взорвать всю страну.
Страна представляет собой $$$n$$$ городов, соединенных двусторонними дорогами. Из любого города можно добраться до любого другого, используя дороги.
Если бомба взорвётся в городе $$$a$$$, то этот город будет уничтожен. Также могут быть уничтожены города, которые соединены дорогой с $$$a$$$. Джонни может выбрать какие именно города будут уничтожены. Обратите внимание, что должен быть уничтожен хотя бы один город, соединенный дорогой с $$$a$$$. Каждый город должен быть уничтожен ровно один раз.
Вам требуется помочь Джонни и определить, возможно ли уничтожить страну. Если это возможно, то необходимо для каждой бомбы установить города, которые будут ей уничтожены. Не требуется минимизировать число бомб.
В первой строке входных данных содержится два целых числа $$$n$$$ и $$$m$$$ — количество городов и дорог ($$$1 \leqslant n \leqslant 100\,000, 0 \leqslant m \leqslant 100\,000$$$). В следующих $$$m$$$ строках дано описание дорог. Каждая из них содержит два целых числа $$$a$$$ и $$$b$$$, которые обозначают, что города $$$a$$$ и $$$b$$$ связаны дорогой ($$$1 \leqslant a, b \leqslant n; a \neq b$$$). Гарантируется, что между каждой парой городов существует не более одной дороги.
В первой строке выходных данных выведите «-1», если решения не существует. Иначе выведите одно целое число $$$k$$$ — количество городов, которые нужно заминировать. В последующих строках выведите описание каждой бомбы в следующем формате:
В первой строке выведите одно целое число $$$t$$$ — количество городов, которые будут уничтожены ($$$2 \leqslant t \leqslant n$$$). Во второй строке выведите $$$t$$$ целых чисел — номера городов, которые будут уничтожены. Обратите внимание, что первым следует выводить город, который будет заминирован.
Каждый город должен быть уничтожен ровно один раз. Если существует несколько решений, выведите любое.
4 4
1 2
2 3
3 1
3 4
1
4
3 1 2 4
5 5
3 4
4 5
1 2
2 3
3 1
2
2
2 1
3
4 3 5