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.
Drzewem nazywamy graf nieskierowany, w którym każde dwa wierzchołki są połączone dokładnie jedną ścieżką prostą, czyli ścieżką bez powtarzających się wierzchołków.
Rozważmy -wierzchołkowe drzewo, w którym wierzchołki są ponumerowane od 1 do . Niech będzie dowolną permutacją zbioru wierzchołków tego drzewa (czyli funkcją różnowartościową ). Permutację nazywamy automorfizmem, jeżeli dla dowolnych dwóch wierzchołków drzewa, wierzchołki i są połączone krawędzią wtedy i tylko wtedy, gdy wierzchołki i są połączone krawędzią.
W tym zadaniu interesuje nas liczba automorfizmów danego drzewa, a dokładniej, reszta z dzielenia tej liczby przez .
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę wierzchołków drzewa. Każdy z kolejnych wierszy zawiera dwie liczby całkowite i (), reprezentujące krawędź łączącą wierzchołki i .
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą: resztę z dzielenia liczby automorfizmów wyjściowego drzewa przez .
Dla danych wejściowych:
6 1 3 2 3 3 4 4 5 4 6
poprawną odpowiedzią jest:
8
Wyjaśnienie do przykładu: Przedstawione drzewo ma 8 automorfizmów. Trzy przykładowe z nich to:
Autor zadania: Adam Malinowski.