Automorfizmy [B]
Limit pamięci: 128 MB
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 .
Wejście
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 .
Wyjście
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 .
Przykład
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.