Canmuu와 친구들은 많은 플루토늄을 얻어 캐나다 야생지 깊숙한 교차로에 새 보물을 묻기로 했습니다. 보물을 묻으려면 지도가 필요하므로 직접 만듭니다.

도로망은 $N$ $(4 \le N \le 100,000)$개 교차로(번호 $1..N$)와 $N$개 길입니다. 붐비는 교차로는 모두를 혼란스럽게 하므로 각 교차로에는 최소 1개, 최대 4개 길이 있습니다. 훌륭한 관리로 무스는 어떤 두 교차로 사이도 양방향으로 달릴 수 있습니다. Canmuu는 교통이 비밀을 줄이므로 사거리에 플루토늄을 묻지 않습니다.

지도에는 모든 길과 교차로가 있지만 위치를 숨기려고 보물이 묻힌 교차로만 표시합니다. 물론 큰 빨간 'X'입니다.

주의 깊은 무스 Canmuu는 장소별 시험 지도를 그려 서로 다른 두 장소에서도 비슷한 지도가 나옴을 알아챘습니다. 호기심이 생긴 무리는 서로 다른 지도가 몇 개일지 조사했습니다.

다음 대응을 만들 수 있으면 지도는 같습니다.

• 양쪽의 X 교차로가 대응합니다.

• 다른 교차로에도 대응을 만들어

• 교차로 대응을 정하면 그들을 잇는 길도 대응합니다.

아래는 $N = 4$ 예로 네 교차로 어디든 묻을 수 있습니다.

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

마지막 두 지도는 같습니다. 정점을 대응시키면(지도를 뒤집어 보세요) 길도 정확히 대응합니다. 따라서 서로 다른 지도는 세 개입니다.

주어진 길들로 서로 다른 지도는 몇 개 가능한가요?

*처음 10번 제출에는 추가 피드백이 주어집니다.

입력

표준 입력에서 읽습니다.

• 1번 줄: 정수 하나 $N$.

• 2..$N + 1$번 줄: 공백으로 구분한 두 정수 $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$, 교차로 $A$, $B$를 잇는 길.

출력

표준 출력에 씁니다.

• 1번 줄: 서로 다른 보물 지도 수를 정수 하나로 출력합니다.

예제

입력 1

4
1 2
2 3
3 1
1 4

출력 1

3

참고

길과 교차로의 그림입니다.

                   4---1---2
                        \ /
                         3

어디든 묻을 수 있지만 2와 3은 같은 지도가 됩니다. 서로 다른 지도는 총 3개입니다.

문제 작성: Yang Yi, 2007