Canmuu und Freunde haben einen großen Plutoniumvorrat erhalten und wollen den neuen Schatz an einer Kreuzung tief in Kanadas Wildnis vergraben. Jeder vergrabene Schatz braucht eine Karte, also erstellen sie ihre eigene.

Das Netz hat $N$ $(4 \le N \le 100,000)$ Kreuzungen (Nummern $1..N$) und $N$ Straßen. Belebte Kreuzungen verwirren alle; jede hat eine bis vier Straßen. Gute Wartung ermöglicht einem Elch, zwischen jedem Paar in beide Richtungen zu laufen. Canmuu vergräbt nichts an Vierwegekreuzungen: Verkehr verringert die Geheimhaltung.

Die Karte enthält alle Straßen und Kreuzungen, doch zur Geheimhaltung wird nur der Schatzort markiert, natürlich mit einem großen roten 'X'.

Der aufmerksame Elch Canmuu zeichnete Probekarten für verschiedene Orte und sah, dass zwei Orte ähnliche Karten ergeben konnten. Neugierig begann die Herde, die möglichen verschiedenen Karten zu zählen.

Karten sind gleich, wenn eine Zuordnung möglich ist, sodass:

• die mit X markierten Kreuzungen einander entsprechen;

• die übrigen Kreuzungen so zugeordnet werden können, dass

• nach Wahl der Kreuzungszuordnung auch die verbindenden Straßen entsprechen.

Beispiel unten mit $N = 4$: An jeder der vier Kreuzungen darf der Schatz liegen.

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

Die letzten zwei sind gleich: Ordne die Knoten zu (betrachte die Karte kopfüber), dann entsprechen die Straßen genau. Nur drei Karten sind verschieden.

Wie viele verschiedene Karten sind bei gegebenen Straßen möglich?

*Die ersten 10 Einsendungen erhalten zusätzliche Rückmeldungen.

Eingabe

Lies von der Standardeingabe.

• Zeile 1: eine ganze Zahl $N$.

• Zeilen 2..$N + 1$: zwei durch Leerzeichen getrennte ganze Zahlen $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$, Straße zwischen $A$, $B$.

Ausgabe

Schreibe auf die Standardausgabe.

• Zeile 1: eine ganze Zahl, Zahl verschiedener Schatzkarten.

Beispiele

Eingabe 1

4
1 2
2 3
3 1
1 4

Ausgabe 1

3

Hinweis

Zeichnung der Straßen und Kreuzungen:

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

Jede Kreuzung ist möglich, doch 2 und 3 ergeben gleiche Karten. Insgesamt sind 3 verschieden.

Aufgabenautor: Yang Yi, 2007