Skojarzenia

Limit pamięci: 32 MB

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 .

Wejście

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 ().

Wyjście

W pierwszym wierszu wyjścia należy wypisać rozmiar najliczniejszego skojarzenia w drzewie. W drugim wierszu należy wypisać liczbę najliczniejszych skojarzeń modulo .

Przykład

Dla danych wejściowych:

5
1 2
3 2
4 5
1 4
1

poprawną odpowiedzią jest:

2
3

Autor zadania: Tomasz Idziaszek.