Zadanie: LIN

Linie autobusowe

Tura 3, plik źródłowy lin.*, dostępna pamięć 32 MB

03 marca 2005

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.

Zadanie

Napisz program, który:

• wczyta opis sieci dróg,

• zaprojektuje sieć linii autobusowych spełniającą podane wymagania,

• wypisze wynik.

Wejście

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 we-jś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.

Wyjście

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ę li równą liczbie miast na trasie i-tej linii, a następnie li 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.

Przykład

Dla danych wejściowych:

4 6

1

1 2

2 4

2 3

1 3

3 4

1 4

poprawnym wynikiem jest:

2

6 2 1 3 2 4 3

2 1 4

1

2

3

4

2