Canmuu e amigos obtiveram grande estoque de plutônio e decidiram enterrar o novo tesouro num cruzamento no interior selvagem canadense. Todo tesouro enterrado pede um mapa, então criarão o próprio.

A rede tem $N$ $(4 \le N \le 100,000)$ cruzamentos (números $1..N$) e $N$ estradas. Cruzamentos movimentados confundem todos; cada um tem uma a quatro estradas. A boa manutenção permite ao alce correr nos dois sentidos entre qualquer par. Canmuu não enterrará em cruzamentos de quatro vias: o tráfego reduz o segredo.

O mapa contém todas as estradas e cruzamentos, mas para ocultar o lugar só marca o do tesouro, claro, com um grande 'X' vermelho.

O atento alce Canmuu desenhou mapas de teste para locais diferentes e notou que dois locais podiam dar mapas semelhantes. Curioso, o grupo começou a contar quantos mapas distintos poderiam criar.

São iguais se houver uma correspondência tal que:

• os cruzamentos com X se correspondam;

• os outros possam se corresponder de modo que

• escolhida a correspondência entre cruzamentos, as estradas que os ligam também correspondam.

Exemplo abaixo com $N = 4$: pode enterrar em qualquer dos quatro cruzamentos.

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

Os últimos dois são iguais: associe os vértices (vire o mapa de cabeça para baixo) e as estradas correspondem exatamente. Só há três distintos.

Quantos mapas distintos são possíveis para um conjunto de estradas?

*As primeiras 10 submissões receberão comentários adicionais.

Entrada

Leia da entrada padrão.

• Linha 1: um inteiro $N$.

• Linhas 2..$N + 1$: dois inteiros $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ separados por espaço, estrada entre $A$, $B$.

Saída

Escreva na saída padrão.

• Linha 1: um inteiro, número de mapas de tesouro distintos.

Exemplos

Entrada 1

4
1 2
2 3
3 1
1 4

Saída 1

3

Nota

Desenho das estradas e cruzamentos:

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

Pode enterrar em qualquer cruzamento, mas 2 e 3 dão mapas idênticos. O total de distintos é 3.

Créditos do problema: Yang Yi, 2007