8420번 - Linie autobusowe 다국어

W Bajtocji jest n miast połączonych dwukierunkowymi drogami, przy których leżą liczne wioski. Król Bajtazar zdecydował się utworzyć sieć linii autobusowych obsługujących miasta i wioski. Każda linia może się zaczynać i kończyć w dowolnym mieście oraz przebiegać przez dowolne miasta. Miasta na trasie linii mogą się powtarzać. Jednak żadna linia nie może przebiegać wielokrotnie tą samą drogą.

Aby wszystkim mieszkańcom zapewnić transport, a jednocześnie zminimalizować koszty inwestycji, król Bajtazar postanowił, że każdą drogą będzie przebiegała dokładnie jedna linia autobusowa, a także, że liczba linii autobusowych będzie minimalna.

Napisz program, który:

• wczyta opis sieci dróg,
• zaprojektuje sieć linii autobusowych spełniającą podane wymagania,
• wypisze wynik.

Pierwszy wiersz zawiera dwie liczby całkowite n i m oddzielone pojedynczym odstępem, 2 ≤ n ≤ 10 000, n - 1 ≤ m ≤ 200 000; n jest liczbą miast, a m liczbą dróg. Miasta są ponumerowane od 1 do n. Kolejnych m wierszy zawiera opis sieci dróg. Każdy z tych wierszy zawiera dwie liczby całkowite a i b oddzielone pojedynczym odstępem, 1 ≤ a < b ≤ n - numery miast połączonych drogą. Każda droga jest podana na wejściu dokładnie raz. Możesz założyć, że dowolne dwa miasta są połączone co najwyżej jedną drogą (chociaż może być wiele tras łączących dwa miasta) i że istnieje możliwość przejazdu pomiędzy dowolnymi dwoma miastami.

Pierwszy wiersz powinien zawierać liczbę c, równą minimalnej liczbie linii autobusowych. Kolejnych c wierszy powinno zawierać opisy kolejnych linii: i + 1-szy wiersz powinien zawierać liczbę l_i równą liczbie miast na trasie i-tej linii, a następnie l_i numerów tych miast, podanych w kolejności przebiegu linii. Liczby w wierszach powinny być pooddzielane pojedynczymi odstępami. Jeżeli linia ma swój początek i koniec w tym samym mieście, jego numer powinien się znaleźć na początku i na końcu opisu trasy.