W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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 polega na napisaniu programu, który:
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 .
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).
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.