Листоноша Леді

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

Місто, в якому живе Леді, поділено на поштові райони. Поштовий район має мережу доріг, що зв'язують перехрестя, де знаходяться будинки мешканців району. Кожною дорогою можна пройти в обидва боки. В кожному районі довільна кількість людей може бути прийнята для роботи в поштових службах.

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

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$.