Canmmu y sus amigos han adquirido recientemente una reserva grande de plutonio y han acordado enterrar su tesoro recién encontrado en alguna intersección de caminos muy adentro en los bosques canadienses. Cualquier entierro de tesoro llama por un mapa del tesoro, por lo tanto ellos han decidido crear uno de su propiedad.

La red de caminos consiste de ~N (4 \leq N \leq 100,000)~ intersecciones con ~N~ caminos conectándolos. Como las intersecciones ocupadas confunden a todo el mundo, cada intersección tiene al menos un camino que llega a ella, y ninguna intersección tiene más de cuatro caminos conectados a ella. El excelente mantenimiento ha asegurado que un reno pueda siempre recorrer cualquier camino entre cualquier par de intersecciones. Aún más, Canmuu ha decidido que el plutonio no debería ser enterrado en cualquiera de las intersecciones de 4 caminos desde que el tráfico pesado disminuye el secreto del tesoro escondido.

El mapa del tesoro contendrá todos los caminos y todas las intersecciones. Pero, para ocultar la ubicación del tesoro, solamente una intersección del mapa de tesoro será rotulada: la intersección en la cual está enterrado el tesoro (la cual tiene una gran ~'X'~ roja, por supuesto).

El reno siempre alerta, Canmuu, dibujó algunos mapas de prueba para ver como se verían dependiendo de donde estaría enterrado el tesoro. Canmuu se dio cuenta que los renos podrían dibujar mapas similares aún si ellos enterraban su tesoro en dos ubicaciones distintas. Les picó la curiosidad, y la manada comenzó tratando de encontrar cuántos mapas diferentes podrían terminar haciendo.

Los mapas son indistinguibles si es posible asignar una correspondencia de tal manera que:

• la intersección rotulada con ~X~ en ambos mapas corresponde
• se puede crear una correspondencia para las otras intersecciones, de tal manera que
• cuando se determine la correspondencia bien-elegida, los caminos que conecten las intersecciones también correspondan.

Por ejemplo, considere los mapas mostrados a continuación con ~N=4~, el tesoro podría estar enterrado en cualquiera de las cuatro interseciones:

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

Los dos mapas finales, sin embargo, no son distintos desde que uno puede crear una correspondencia para los vértices (considere el mapa con la parte de arriba abajo) y entonces los caminos corresponden exactamente. Por lo tanto, solo 3 mapas son distintos.

¿Cuántos mapas distintos son posibles para un conjunto dado de caminos?

Entrada

• Línea 1: un solo entero: ~N~
• Líneas 2..N+1: Dos enteros separados por espacio: ~A~ y ~B ( 1 \leq A \leq N, 1 \leq B \leq N)~, indicando que hay un camino conectando la intersección ~A~ y la intersección ~B~.

Ejemplo de Entrada

4
1 2
2 3
3 1
1 4

Detalles de la Entrada

Aquí hay un dibujo de los caminos y las intersecciones:

Salida

El número de mapas de tesoro distintos.

Ejemplo de Salida

3

Detalles de la Salida

El tesoro podría enterrarse en cualquier intersección. Sin embargo, enterarlo en las intersecciones 2 y 3 produce mapas que son idénticos. Por lo tanto el número total de mapas del tesoro distintos es 3.