Pentru un graf neorientat G, un arbore partial este un subgraf conex, fara cicluri, care contine acelasi numar de noduri ca G si doar muchii din G (nu neaparat toate).
Se citeste un graf neorientat G cu n noduri (numerotate de la 0 la n-1) si m muchii. Determinati numarul de arbori partiali ai lui G.
- Date de intrare
- Pe prima linie se citesc doua numere naturale n si m. Pe fiecare dintre urmatoarele m linii se citesc doua numere u v (0 <= u, v <= n-1), reprezentand o muchie intre nodurile u si v. Graful nu contine muchii multiple sau autobucle.
- Date de iesire
- Se afiseaza un singur numar natural, numarul de arbori partiali ai grafului.
- Restrictii
- 2 <= n <= 8 n-1 <= m <= 15 Graful dat este conex.
Exemple
Exemplul 1
Intrare
5 6 1 3 3 2 1 4 4 2 2 0 4 0
Iesire
11
Exemplul 2
Intrare
3 3 0 1 1 2 0 2
Iesire
3