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

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

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

Рассмотрим ухо v₀−v₁−...−v_k и удалим из графа все его ребра и промежуточные вершины (v₁, v₂, ... , v_k−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.

Примеры

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

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