보물

시간 제한1초메모리 제한128 MB

요약

정점 N개와 간선 N개를 가진 연결 그래프(차수 최대 4)에서, 차수가 4가 아닌 각 정점을 뿌리로 삼았을 때 서로 동형이 아닌 경우의 수를 센다.

난이도: 어려움10점 중 8점
유형: 그래프, 트라이, DFS, 해시맵
정답자: 아직 제출이 없습니다

문제

칸무와 친구들은 많은 양의 플루토늄을 손에 넣었고, 이 보물을 캐나다 오지의 어느 도로 교차로에 묻기로 했습니다. 보물을 묻으려면 보물 지도가 필요하므로 이들은 직접 지도를 그리기로 합니다.

도로망에는 $1$ 번부터 $N$ 번까지 번호가 매겨진 교차로 $N$ 개가 있고, 정확히 $N$ 개의 도로가 이들을 잇습니다. 모든 교차로에는 도로가 최소 $1$ 개, 최대 $4$ 개 연결되어 있으며, 도로망은 연결되어 있어 어떤 두 교차로 사이든 오갈 수 있습니다. 통행량이 많으면 비밀이 새어 나가므로 보물은 절대 4거리 교차로(도로가 정확히 $4$ 개인 교차로)에는 묻지 않습니다.

지도에는 모든 도로와 모든 교차로가 그려지지만, 위치를 숨기기 위해 오직 한 교차로에만 커다란 빨간 "X" 표시를 합니다. 바로 보물이 묻힌 곳입니다.

칸무는 묻을 수 있는 각 위치마다 시험 삼아 지도를 그려 보다가, 서로 다른 두 위치에 묻어도 똑같이 보이는 지도가 나올 수 있음을 알아챕니다. 무리는 과연 정말로 서로 다른 지도가 몇 장 나올 수 있는지 궁금해집니다.

두 지도는 다음을 만족하도록 한 지도의 교차로들을 다른 지도의 교차로들과 일대일로 대응시킬 수 있을 때 같은 지도로 봅니다.

X 표시가 된 두 교차로가 서로 대응되고,
이 대응 아래에서 한 지도의 모든 도로가 다른 지도의 도로와 대응됩니다.

예를 들어 $N = 4$ 일 때, 보물은 네 교차로 중 어디에나 묻을 수 있습니다.

        +             +             X           +
       /|            /|            /|          /|
  X---+ |       +---X |       +---+ |     +---+ |
       \|            \|            \|          \|
        +             +             +           X

마지막 두 지도는 서로 다르지 않습니다. 한쪽을 위아래로 뒤집으면 모든 교차로와 모든 도로가 그대로 대응되기 때문입니다. 따라서 네 지도 중 서로 다른 것은 세 장뿐입니다.

도로망이 주어질 때, 서로 다른 보물 지도가 몇 장 나올 수 있는지 구하세요.

제약: $4 \le N \le 100{,}000$ 이고, 각 교차로에는 도로가 $1$ 개 이상 $4$ 개 이하로 연결되며, 도로망은 연결되어 있고 도로는 정확히 $N$ 개입니다.

입력

첫째 줄: 정수 $N$ 하나.
둘째 줄부터 $N+1$ 째 줄까지: 공백으로 구분된 두 정수 $A$ 와 $B$ ( $1 \le A \le N$ , $1 \le B \le N$ ). 교차로 $A$ 와 $B$ 를 잇는 도로가 있음을 뜻합니다.

출력

서로 다른 보물 지도의 수를 나타내는 정수 하나.

예제3

예제 1
입력
```
4
1 2
2 3
3 1
1 4
```
예상 출력
```
3
```
예제 2
입력
```
3
1 2
2 3
3 1
```
예상 출력
```
1
```
예제 3
입력
```
4
1 2
2 3
3 4
4 1
```
예상 출력
```
1
```