In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
Napisz program, który:
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.
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.
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.