eolymp
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