Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Отрезание ушей

(Время: 5 сек. Память: 64 Мб Сложность: 80%)

Рассмотрим связный неориентированный граф без петель и параллельных ребер. Будем называть число ребер, инцидентных вершине v, ее степенью и обозначать степень вершины как deg v.

Простой путь v0−v1−...−vk, такой что deg v0 ≥ 2, deg vk ≥ 2, и для всех i от 1 до k−1 выполнено deg vi = 2, называется ухом. В частности, если k = 1, то ребро v0−v1, соединяющее две вершины степени хотя бы 2, также образует ухо. Вершины v0 и vk могут совпадать.

Рассмотрим ухо v0−v1−...−vk и удалим из графа все его ребра и промежуточные вершины (v1, v2, ... , vk−1) Будем называть такую операцию отрезанием уха. Если у уха нет промежуточных вершин, то его отрезание состоит в удалении его единственного ребра.

Ушной декомпозицией графа G называется последовательность отрезаний ушей, такая, что после каждого отрезания граф остается связным, и после окончания процесса граф состоит из единственной вершины.

По заданному графу G найдите его ушную декомпозицию, либо установите, что у графа ее нет.

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

Первая строка входного файла INPUT.TXT содержит n и m – количество вершин и ребер графа G, соответственно (2 ≤ n ≤ 20 000, n−1 ≤ m ≤ 100 000). Пусть вершины графа пронумерованы от 1 до n. Следующие m строк описывают ребра графа, каждая строка содержит два числа номера вершин, соединенных соответствующим ребром. Гарантируется, что G связен, никакие две вершины не соединены более чем одним ребром, никакое ребро не соединяет вершину саму с собой.

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

На первой строке выходного файла OUTPUT.TXT выведите d – количество отрезаний ушей в некоторой ушной декомпозиции графа G. Следующие d строк должны описывать отрезания. Каждое отрезание уха описывается числом k – количеством ребер в соответствующем ухе, за которым следует k+1 число – вершины в ухе в том порядке, в котором они в нем следуют. Если у графа отсутствует ушная декомпозиция, выведите d = −1.

Примеры

INPUT.TXTOUTPUT.TXT
15 8
1 2
2 3
3 5
5 1
2 4
4 1
3 4
4 5
4
1 1 4
1 3 4
2 2 4 5
4 1 5 3 2 1
23 2
1 2
1 3
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru