Sznurki
Limit pamięci: 32 MB
Przedsiębiorstwo String-Toys S.A. zwróciło się do Ciebie o pomoc
w rozwiązaniu następującego problemu.
String-Toys S.A. chce produkować ze sznurka
modele spójnych grafów acyklicznych.
Każdy graf składa się z wierzchołków i pewnej liczby krawędzi
łączących różne wierzchołki.
Ten sam wierzchołek może być połączony z wieloma innymi wierzchołkami.
Graf jest spójny i acykliczny,
gdy od każdego wierzchołka można przejść do każdego innego
wierzchołka wędrując po krawędziach i
co więcej, bez zawracania można to zrobić dokładnie na jeden sposób.
Wierzchołki grafów mają być modelowane przez węzły zawiązane
na kawałkach sznurka,
a krawędzie przez odcinki sznurka pomiędzy węzłami.
Każdy węzeł może być wynikiem zasuplenia kawałka sznurka
lub związania w tym samym miejscu wielu kawałków.
Ze względów technicznych koszty produkcji zależą od liczby kawałków
sznurka użytych do wykonania modelu, oraz od długości najdłuższego
z kawałków.
(Każda krawędź ma długość 1.
Długość sznurka użytego do zrobienia węzłów jest pomijalna.)
Zadanie
Zadanie polega na napisaniu programu, który:
-
wczyta ze standardowego wejścia opis spójnego grafu
acyklicznego, który ma być modelowany,
- obliczy:
-
minimalną liczbę kawałków sznurka potrzebnych do wykonania
modelu,
-
zakładając, że liczba kawałków sznurka jest minimalna,
minimalną długość najdłuższego kawałka sznurka
potrzebnego do wykonania modelu,
-
wypisze dwie obliczone liczby na standardowe wyjście.
Wejście
Pierwszy wiersz zawiera jedną dodatnią liczbę całkowitą -
liczbę wierzchołków w grafie, .
Wierzchołki są ponumerowane od 1 do .
Kolejne wierszy zawiera opisy krawędzi, po jednej w wierszu.
Każdy z tych wierszy zawiera parę liczb całkowitych i
oddzielonych pojedynczym odstępem, , .
Para taka reprezentuje krawędź łączącą wierzchołki i .
Wyjście
Twój program powinien wypisać w pierwszym wierszu
wyjścia dwie liczby całkowite i oddzielone pojedynczym
odstępem:
powinno być minimalną liczbą kawałków sznurka potrzebnych do
wykonania modelu grafu, a powinno być minimalną długością
najdłuższego kawałka sznurka (zakładając, że zużyliśmy kawałków
sznurka).
Przykład
Dla danych wejściowych:
9
7 8
4 5
5 6
1 2
3 2
9 8
2 5
5 8
poprawną odpowiedzią jest:
4 2
Autor zadania: Marcin Kubica.