In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.