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
Dla danych wejściowych:
4 6
1 2
2 4
2 3
1 3
3 4
1 4
poprawną odpowiedzią jest:
2
6 2 1 3 2 4 3
2 1 4
Autor zadania: Bartosz Walczak.