Canmuu et ses amis ont acquis une grande réserve de plutonium et vont enfouir leur nouveau trésor à un carrefour au fond de la nature canadienne. Tout trésor enterré exige une carte ; ils créeront la leur.

Le réseau a $N$ $(4 \le N \le 100,000)$ carrefours (numéros $1..N$) et $N$ routes. Les carrefours animés troublent tout le monde ; chacun a une à quatre routes. Un excellent entretien permet à un élan de courir dans les deux sens entre toute paire. Canmuu n’enfouira pas le plutonium aux carrefours à quatre routes : le trafic nuit au secret.

La carte contient toutes les routes et tous les carrefours, mais pour cacher le lieu, seul celui du trésor porte une marque, évidemment un grand 'X' rouge.

Toujours attentif, l’élan Canmuu dessina des cartes d’essai pour différents lieux. Il constata que deux lieux pouvaient donner des cartes semblables. Intrigué, le troupeau chercha combien de cartes distinctes seraient possibles.

Des cartes sont identiques s’il existe une correspondance telle que :

• les carrefours marqués X se correspondent ;

• les autres carrefours peuvent se correspondre de sorte que

• une fois les carrefours associés, les routes les reliant se correspondent aussi.

Exemple ci-dessous, $N = 4$ : le trésor peut être à n’importe lequel des quatre carrefours.

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

Les deux dernières sont identiques : on peut associer les sommets (retournez la carte), puis les routes correspondent exactement. Il n’y a que trois cartes distinctes.

Combien de cartes distinctes pour un ensemble donné de routes ?

*Les 10 premières soumissions auront des retours supplémentaires.

Entrée

Lisez sur l’entrée standard.

• Ligne 1 : un entier $N$.

• Lignes 2..$N + 1$ : deux entiers $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ séparés par un espace, route entre $A$, $B$.

Sortie

Écrivez sur la sortie standard.

• Ligne 1 : un entier, nombre de cartes distinctes.

Exemples

Entrée 1

4
1 2
2 3
3 1
1 4

Sortie 1

3

Remarque

Voici les routes et les carrefours dessinés.

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

On peut enfouir le trésor partout, mais les carrefours 2 et 3 donnent des cartes identiques. Il y en a donc 3 distinctes.

Auteur du problème : Yang Yi, 2007