Linie autobusowe

Limit pamięci: 32 MB

W Bajtocji jest 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 i oddzielone pojedynczym odstępem, , ; jest liczbą miast, a liczbą dróg. Miasta są ponumerowane od 1 do . Kolejnych wierszy zawiera opis sieci dróg. Każdy z tych wierszy zawiera dwie liczby całkowite i oddzielone pojedynczym odstępem, - 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.

Wyjście

Pierwszy wiersz powinien zawierać liczbę , równą minimalnej liczbie linii autobusowych. Kolejnych wierszy powinno zawierać opisy kolejnych linii: -szy wiersz powinien zawierać liczbę równą liczbie miast na trasie -tej linii, a następnie 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

4 6
1 2
2 4
2 3
1 3
3 4
1 4

2
6 2 1 3 2 4 3
2 1 4

Autor zadania: Bartosz Walczak.