Почтальон Леди

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

Город, в котором живет Леди, разделен на почтовые районы. В каждом районе есть сеть дорог, соединяющих перекрестки, где расположены дома жителей. По каждой дороге можно двигаться в обоих направлениях. В каждом районе можно нанять любое количество почтальонов.

Каждое утро почтальоны получают портфели с письмами, которые нужно доставить по маршруту, проходящему через определенные улицы района. Каждый маршрут должен соответствовать следующим условиям, установленным Леди:

1. Маршрут начинается и заканчивается на одном и том же перекрестке.

2. Маршрут не должен проходить через один и тот же перекресток более одного раза.

3. Маршрут не должен пересекаться с другими маршрутами, то есть каждая дорога должна обслуживаться только одним почтальоном.

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

Леди отвечает за составление маршрутов для почтальонов и может нанять любое количество сотрудников. Она просит вас помочь найти набор маршрутов для почтальонов, которые будут соответствовать всем условиям для определенных почтовых районов.

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

Первая строка содержит два целых числа $n$ и $m$ ($3\le n\le 5\cdot 10^5$, $3\le m\le 5\cdot 10^5$) — количество перекрестков и количество дорог.

Каждая из следующих $m$ строк содержит два целых числа $u$ и $v$ ($1\le u,v\le n,u\ne v$) — перекрестки, между которыми существует дорога.

Во входных данных соблюдаются следующие условия:

1. Между любыми двумя перекрестками может быть не более одной дороги.

2. Между любыми двумя перекрестками существует путь, который может проходить через одну или более дорог.

3. Всегда существует решение, то есть Леди всегда может найти набор маршрутов, которые будут удовлетворять всем условиям.

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

В первой строке выведите одно целое число $d$ ($1\le d\le m$) — количество маршрутов.

В каждой из следующих $d$ строк выведите одно целое число $w$ ($1\le w\le m$) — количество перекрестков в маршруте, затем выведите $w$ целых чисел $l_1,l_2,\dots ,l_w$ ($1\le l_i\le n$) — номера перекрестков. Перекрестки должны быть перечислены в том порядке, в котором почтальон будет их обходить. Перекресток, на котором начинается и заканчивается маршрут, должен быть указан только один раз в начале маршрута.

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

Примеры

Оценивание

1. ($38$ баллов): $3\le n\le 2000,3\le m\le 10^5$;

2. ($17$ баллов): $3\le n\le 10^5,3\le m\le 10^5$;

3. ($45$ баллов): $3\le n\le 5\cdot 10^5,3\le m\le 5\cdot 10^5$.