Problems
Листоноша Леді
Листоноша Леді
Леді після школи працює листоношею. Це неймовірно цікава робота для Леді, і вона працює вже досить давно. Леді~--- найдосвідченіша листоноша, тому вона контролює, аби усі листи надходили без затримок й будує маршрути для листонош.
Місто, в якому живе Леді, поділено на поштові райони. Поштовий район має мережу доріг, що зв'язують перехрестя, де знаходяться будинки мешканців району. Кожною дорогою можна пройти в обидва боки. В кожному районі довільна кількість людей може бути прийнята для роботи в поштових службах.
Щоранку, кожен листоноша отримує портфель з листами, що мають бути доставлені вздовж маршруту, що проходить деякими вулицями району. Кожен маршрут має задовольняти умови, які вигадала Леді:
\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}
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