eolymp
bolt
Try our new interface for solving problems
Məsələlər

Минер

Минер

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Агент Джонни Инглиш учился в школе разведки. Однажды в качестве задания ему было предложено заминировать некоторые города, чтобы взорвать всю страну.

Страна представляет собой n городов, соединенных двусторонними дорогами. Из любого города можно добраться до любого другого, используя дороги.

Если бомба взорвётся в городе a, то этот город будет уничтожен. Также могут быть уничтожены города, которые соединены дорогой с a. Джонни может выбрать какие именно города будут уничтожены. Обратите внимание, что должен быть уничтожен хотя бы один город, соединенный дорогой с a. Каждый город должен быть уничтожен ровно один раз.

Вам требуется помочь Джонни и определить, возможно ли уничтожить страну. Если это возможно, то необходимо для каждой бомбы установить города, которые будут ей уничтожены. Не требуется минимизировать число бомб.

Giriş verilənləri

В первой строке содержится два целых числа n и m (1n, m10^5) - количество городов и дорог. В следующих m строках дано описание дорог. Каждая из них содержит два целых числа a и b, которые обозначают, что города a и b (1a, bn, ab) связаны дорогой. Гарантируется, что между каждой парой городов существует не более одной дороги.

Çıxış verilənləri

В первой строке выведите -1, если решения не существует. Иначе выведите одно целое число k - количество городов, которые нужно заминировать. В последующих строках выведите описание каждой бомбы в следующем формате:

В первой строке выведите одно целое число t (2tn) - количество городов, которые будут уничтожены. Во второй строке выведите t целых чисел — номера городов, которые будут уничтожены. Обратите внимание, что первым следует выводить город, который будет заминирован.

Каждый город должен быть уничтожен ровно один раз. Если существует несколько решений, выведите любое.

Nümunə

Giriş verilənləri #1
4 4
1 2
2 3
3 1
3 4
Çıxış verilənləri #1
1
4
3 1 2 4
Giriş verilənləri #2
5 5
3 4
4 5
1 2
2 3
3 1
Çıxış verilənləri #2
2
2
2 1 
3
4 3 5 
Mənbə 2018 Цикл Интернет-олимпиад для школьников, первая командная олимпиада сезона, 14 октября, Задача I