Un puzzle culisant are N pozitii numerotate de la 1 la N, legate intre ele printr-un graf de M conexiuni directe. In N-1 dintre pozitii se afla piese etichetate distinct, iar o pozitie ramane libera. O mutare consta in deplasarea unei piese dintr-o pozitie vecina (conform grafului) in pozitia libera. Configuratia de referinta are pozitia P libera, iar celelalte pozitii contin piesele etichetate 1, 2, ..., N-1 in ordinea crescatoare a indicelui pozitiei. Se considera toate cele (N-1)! configuratii initiale in care pozitia libera este tot P, iar piesele sunt asezate intr-o ordine oarecare in celelalte pozitii. Determinati din cate astfel de configuratii initiale NU se poate ajunge, printr-o succesiune de mutari, la configuratia de referinta.
- Date de intrare
- Pe prima linie se citesc trei numere N, M si P. Urmeaza M linii, fiecare continand doua numere u v (1-indexate), reprezentand o conexiune directa intre pozitiile u si v.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul configuratiilor initiale din care puzzle-ul nu poate fi rezolvat.
- Restrictii
- 3 <= N <= 7, N-1 <= M <= N*(N-1)/2, 1 <= P <= N
Exemple
Exemplul 1
Intrare
4 4 4 1 2 2 3 1 3 1 4
Iesire
4
Exemplul 2
Intrare
3 2 2 1 2 2 3
Iesire
1