Se da un graf neorientat, conex si ponderat, cu n noduri si m muchii. Determinati cati arbori partiali de cost minim (arbori partiali cu suma costurilor muchiilor minima posibila) are graful.
- Date de intrare
- Pe prima linie se citesc doua numere intregi n si m. Pe urmatoarele m linii se citesc cate trei numere intregi u, v si w, insemnand ca exista o muchie intre nodurile u si v cu costul w.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul de arbori partiali de cost minim.
- Restrictii
- 2 <= n <= 9 n - 1 <= m <= 16 1 <= w <= 50 Graful dat este conex.
Exemple
Exemplul 1
Intrare
6 7 2 3 1 5 6 1 1 2 2 1 4 2 4 5 2 2 5 2 3 6 2
Iesire
7
Exemplul 2
Intrare
2 1 1 2 5
Iesire
1