0012. Маршруты

Input file name:	routes.in
Output file name:	routes.out
Time limit:	2 s
Memory limit:	64 megabytes

Город Затропеводск признан большим историческим и культурным центром. В городе N перекрестков и M улиц. Каждая улица соединяет два перекрестка, вне перекрестков улицы не пересекаются. По улице можно двигаться в обоих направлениях.

В целях развития туризма местная администрация решила составить несколько пешеходных туристических маршрутов, проходящих по улицам города. Администрация требует, чтобы каждая улица города присутствовала в одном и только одном маршруте (неважно в каком направлении). Маршрут обязательно должен начинаться и заканчиваться на одном и том же перекрестке. Для экономии бюджетных средств число маршрутов требуется сделать минимально возможным.

Формат входного файла

В первой строке входного файла заданы два числа N и M √ количество перекрестков и улиц в Затропеводске (1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). Далее содержится M строк по два числа в каждой √ номера перекрестков, соединяемых улицей. Гарантируется, что никакая улица не соединяет перекресток с самим собой.

Формат выходного файла

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

Пример:

routes.in	routes.out
3 3 1 2 2 3 3 1	1 3 1 2 3
3 6 1 2 2 3 3 1 1 2 2 3 3 1	1 6 1 2 6 4 5 3
3 2 1 2 2 3	-1

Source: Командное школьное первенство Республики Карелия по программированию, май 2008.

Discuss       Submit a solution