Минер
Минер
Агент Джонни Инглиш учился в школе разведки. Однажды в качестве задания ему было предложено заминировать некоторые города, чтобы взорвать всю страну.
Страна представляет собой n городов, соединенных двусторонними дорогами. Из любого города можно добраться до любого другого, используя дороги.
Если бомба взорвётся в городе a, то этот город будет уничтожен. Также могут быть уничтожены города, которые соединены дорогой с a. Джонни может выбрать какие именно города будут уничтожены. Обратите внимание, что должен быть уничтожен хотя бы один город, соединенный дорогой с a. Каждый город должен быть уничтожен ровно один раз.
Вам требуется помочь Джонни и определить, возможно ли уничтожить страну. Если это возможно, то необходимо для каждой бомбы установить города, которые будут ей уничтожены. Не требуется минимизировать число бомб.
Входные данные
В первой строке содержится два целых числа n и m (1 ≤ n, m ≤ 105
) - количество городов и дорог. В следующих m строках дано описание дорог. Каждая из них содержит два целых числа a и b, которые обозначают, что города a и b (1 ≤ a, b ≤ n, a ≠ b) связаны дорогой. Гарантируется, что между каждой парой городов существует не более одной дороги.
Выходные данные
В первой строке выведите -1, если решения не существует. Иначе выведите одно целое число k - количество городов, которые нужно заминировать. В последующих строках выведите описание каждой бомбы в следующем формате:
В первой строке выведите одно целое число t (2 ≤ t ≤ 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