Canmuu e amici hanno ottenuto una grande scorta di plutonio e deciso di seppellire il nuovo tesoro a un incrocio nella remota natura canadese. Ogni tesoro sepolto richiede una mappa, quindi creeranno la loro.
La rete ha $N$ $(4 \le N \le 100,000)$ incroci (numerati $1..N$) e $N$ strade. Gli incroci trafficati confondono tutti; ognuno ha da una a quattro strade. L’ottima manutenzione permette a un alce di correre in entrambi i sensi fra qualsiasi coppia. Canmuu non seppellirà negli incroci a quattro vie: il traffico riduce la segretezza.
La mappa contiene tutte le strade e gli incroci, ma per celare il luogo marca solo quello del tesoro, ovviamente con una grande 'X' rossa.
L’attento alce Canmuu disegnò mappe di prova per vari luoghi e notò che due luoghi potevano dare mappe simili. Incuriosito, il gruppo iniziò a contare le possibili mappe distinte.
Sono uguali se si può creare una corrispondenza tale che:
gli incroci con X corrispondano;
gli altri incroci possano corrispondere in modo che
scelta la corrispondenza degli incroci, corrispondano anche le strade che li uniscono.
Esempio sotto con $N = 4$: si può seppellire in qualsiasi dei quattro incroci.
+ + X +
/| /| /| /|
X---+ | +---X | +---+ | +---+ |
\| \| \| \|
+ + + XLe ultime due sono uguali: associa i vertici (guarda la mappa capovolta) e le strade corrispondono esattamente. Solo tre sono distinte.
Quante mappe distinte per un insieme dato di strade?
*Le prime 10 consegne riceveranno riscontri aggiuntivi.
Input
Leggi dall’input standard.
Riga 1: un intero $N$.
Righe 2..$N + 1$: due interi $A$, $B$ $(1 \le A \le N; 1 \le B \le N)$ separati da spazio, strada fra $A$, $B$.
Output
Scrivi sull’output standard.
- Riga 1: un intero, numero di mappe del tesoro distinte.
Esempi
Input 1
4 1 2 2 3 3 1 1 4
Output 1
3
Note
Disegno delle strade e degli incroci:
4---1---2
\ /
3Ogni incrocio è possibile, ma 2 e 3 danno mappe identiche. Il totale delle distinte è 3.
Autore del problema: Yang Yi, 2007