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.
Skojarzeniem nazwiemy taki podzbiór krawędzi grafu, że dla każdego wierzchołka co najwyżej jedna krawędź z nim incydentna należy do skojarzenia. Najliczniejszym skojarzeniem nazwiemy skojarzenie o największym możliwym rozmiarze.
Dane jest drzewo o wierzchołkach. Znajdź rozmiar najliczniejszego skojarzenia w tym drzewie oraz liczbę skojarzeń o takim rozmiarze, modulo .
W pierwszym wierszu wejścia znajduje się liczba całkowita oznaczająca liczbę wierzchołków grafu (). Wierzchołki są ponumerowane liczbami od do . W kolejnych wierszach znajdują się opisy krawędzi grafu. Każdy z nich składa się z dwóch liczb i oznaczających, że istnieje krawędź łącząca wierzchołki i (). W ostatnim wierszu znajduje się liczba całkowita ().
W pierwszym wierszu wyjścia należy wypisać rozmiar najliczniejszego skojarzenia w drzewie. W drugim wierszu należy wypisać liczbę najliczniejszych skojarzeń modulo .
Dla danych wejściowych:
5 1 2 3 2 4 5 1 4 1
poprawną odpowiedzią jest:
2 3
Autor zadania: Tomasz Idziaszek.