보물

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

도로망에는 $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$를 잇는 도로가 있음을 뜻합니다.

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