e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

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

Леді після школи працює листоношею. Це неймовірно цікава робота для Леді, і вона працює вже досить давно. Леді~--- найдосвідченіша листоноша, тому вона контролює, аби усі листи надходили без затримок й будує маршрути для листонош. Місто, в якому живе Леді, поділено на поштові райони. Поштовий район має мережу доріг, що зв'язують перехрестя, де знаходяться будинки мешканців району. Кожною дорогою можна пройти в обидва боки. В кожному районі довільна кількість людей може бути прийнята для роботи в поштових службах. Щоранку, кожен листоноша отримує портфель з листами, що мають бути доставлені вздовж маршруту, що проходить деякими вулицями району. Кожен маршрут має задовольняти умови, які вигадала Леді: \begin{enumerate} \item Маршрут починається і закінчується на одному і тому ж перехресті. \item Маршрут ніколи не проходить через одне і те ж перехрестя двічі. \item Маршрут не повинен мати жодну спільну дорогу з будь-яким іншим маршрутом. Тобто будь-яку дорогу має обслуговувати рівно один листоноша. \end{enumerate} Разом, усі листоноші мають обслуговувати район повністю. Кожна дорога має належати рівно одному маршруту. Як Ви вже могли здогадатись, Леді відповідальна за побудову маршрутів листонош. Вона може прийняти на роботу будь-яку кількість листонош. Вона просить вас для певних поштових районів знаходити набір маршрутів для листонош, що будуть задовольняти усім умовам. \InputFile Перший рядок містить два цілі $n$ та $m$ ($3 \leq n \leq 5 \cdot 10^5$, $3 \leq m \leq 5 \cdot 10^5$)~--- кількість перехресть та кількість доріг. Кожен з наступних $m$ рядків містить два цілі числа $u$ та $v$ ($1 \leq u,v \leq n, u \neq v$)~--- перехрестя, між якими існує дорога. У вхідних даних виконуються умови: \begin{enumerate} \item Будь-які два перехрестя з'єднані щонайбільше однією дорогою. \item Між будь-якими двома перехрестями існує шлях, що може проходити через одну або більше доріг. \item Існує розв'язок, тобто Леді завжди може знайти набір маршрутів, що будуть задовольняти усі умови. \end{enumerate} \OutputFile У першому рядку виведіть одне ціле число $d$ ($1 \leq d \leq m$)~--- кількість маршрутів. У кожному з наступних $d$ рядків виведіть одне ціле число $w$ ($1 \leq w \leq m$)~--- кількість перехресть у маршруті, після чого також виведіть $w$ цілих чисел $l_1, l_2, \dots, l_w$ ($1 \leq l_i \leq n$)~--- номери перехресть. Перехрестя мають бути виведені в тому порядку, в якому листоноша буде їх обходити. Перехрестя, на якому починається і закінчується маршрут листоноші має бути виведено лише один раз на початку маршруту. Якщо існує декілька розв'язків, ваша програма може вивести будь-який. \Scoring \begin{enumerate} \item ($38$ балів): $3 \leq n \leq 2000, 3 \leq m \leq 10^5$; \item ($17$ балів): $3 \leq n \leq 10^5, 3 \leq m \leq 10^5$; \item ($45$ балів): $3 \leq n \leq 5 \cdot 10^5, 3 \leq m \leq 5 \cdot 10^5$. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9
Output example #1
3
6 4 8 10 9 2 3
6 5 4 7 6 3 1
3 8 7 5
Author Sofia Melnyk