Canmuu y sus amigos consiguieron una gran reserva de plutonio y acordaron enterrar el nuevo tesoro en un cruce de la naturaleza canadiense. Todo tesoro enterrado necesita mapa, así que crearán el suyo.
La red tiene $N$ $(4 \le N \le 100,000)$ cruces (números $1..N$) y $N$ carreteras. Los cruces concurridos confunden a todos; cada uno tiene de una a cuatro carreteras. El buen mantenimiento permite a un alce correr en ambos sentidos entre cualquier pareja. Canmuu no enterrará en cruces de cuatro vías: el tráfico reduce el secreto.
El mapa tiene todas las carreteras y cruces, pero para ocultar el lugar solo se marca el del tesoro, claro, con una gran 'X' roja.
El atento alce Canmuu dibujó mapas de prueba para distintos lugares y vio que dos lugares podían dar mapas parecidos. Curioso, el grupo comenzó a calcular cuántos mapas distintos podrían crear.
Son iguales si se puede establecer una correspondencia tal que:
los cruces con X se correspondan;
se puedan corresponder los demás cruces de modo que
al elegir la correspondencia entre cruces, las carreteras que los unen también se correspondan.
Ejemplo de abajo con $N = 4$: puede enterrarse en cualquiera de cuatro cruces.
+ + X +
/| /| /| /|
X---+ | +---X | +---+ | +---+ |
\| \| \| \|
+ + + XLos últimos dos son iguales: corresponde los vértices (mira el mapa al revés) y las carreteras coinciden exactamente. Solo hay tres distintos.
¿Cuántos mapas distintos son posibles para unas carreteras dadas?
*Las primeras 10 entregas recibirán comentarios adicionales.
Entrada
Lee de la entrada estándar.
Línea 1: un entero $N$.
Líneas 2..$N + 1$: dos enteros $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ separados por espacio, carretera entre $A$, $B$.
Salida
Escribe en la salida estándar.
- Línea 1: un entero, número de mapas del tesoro distintos.
Ejemplos
Entrada 1
4 1 2 2 3 3 1 1 4
Salida 1
3
Nota
Aquí se dibujan carreteras y cruces.
4---1---2
\ /
3Puede enterrarse en cualquier cruce, pero 2 y 3 dan mapas idénticos. El total de distintos es 3.
Autor del problema: Yang Yi, 2007