Canmuu i przyjaciele zdobyli duży zapas plutonu i postanowili zakopać nowy skarb na skrzyżowaniu głęboko w kanadyjskiej dziczy. Każdy zakopany skarb potrzebuje mapy, więc stworzą własną.
Sieć ma $N$ $(4 \le N \le 100,000)$ skrzyżowań (numery $1..N$) i $N$ dróg. Ruchliwe skrzyżowania dezorientują wszystkich; każde ma od jednej do czterech dróg. Dobra konserwacja pozwala łosiowi biec w obie strony między dowolną parą. Canmuu nie zakopie na skrzyżowaniu czterech dróg: ruch zmniejsza tajność.
Mapa zawiera wszystkie drogi i skrzyżowania, ale dla ukrycia miejsca oznacza tylko miejsce skarbu, oczywiście dużym czerwonym 'X'.
Czujny łoś Canmuu narysował próbne mapy różnych miejsc i zauważył, że dwa miejsca mogą dać podobne mapy. Zaciekawione stado zaczęło liczyć możliwe różne mapy.
Mapy są jednakowe, jeśli można ustalić przyporządkowanie takie, że:
skrzyżowania z X odpowiadają sobie;
pozostałe skrzyżowania da się przyporządkować tak, że
po wybraniu przyporządkowania skrzyżowań odpowiadają też łączące je drogi.
Przykład poniżej z $N = 4$: skarb można zakopać na każdym z czterech skrzyżowań.
+ + X +
/| /| /| /|
X---+ | +---X | +---+ | +---+ |
\| \| \| \|
+ + + XOstatnie dwie są jednakowe: przyporządkuj wierzchołki (odwróć mapę), a drogi dokładnie odpowiadają. Różne są tylko trzy.
Ile różnych map dla danego zbioru dróg?
*Pierwsze 10 zgłoszeń otrzyma dodatkowe informacje zwrotne.
Wejście
Czytaj ze standardowego wejścia.
Wiersz 1: jedna liczba całkowita $N$.
Wiersze 2..$N + 1$: dwie liczby całkowite $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ oddzielone spacją, droga między $A$, $B$.
Wyjście
Pisz na standardowe wyjście.
- Wiersz 1: jedna liczba całkowita, liczba różnych map skarbu.
Przykład
Wejście 1
4 1 2 2 3 3 1 1 4
Wyjście 1
3
Uwagi
Rysunek dróg i skrzyżowań:
4---1---2
\ /
3Każde skrzyżowanie jest możliwe, lecz 2 i 3 dają jednakowe mapy. Łącznie różnych jest 3.
Autor zadania: Yang Yi, 2007