Suntem un grup de iubitori ai muntelui şi plănuim pentru vacanţa mare o expediţie în Apuseni. Studiind atent harta, am observat că există
N cabane, pe care le-am numerotat de la 1 la
N. Pe hartă sunt marcate şi cele
P poteci pe care se poate circula în siguranţă. O potecă uneşte două cabane şi, evident, poate fi parcursă în ambele sensuri.
În Apuseni există multe izvoare subterane şi am observat pe hartă că unele poteci traversează izvoare. Am marcat pe hartă cu 1 potecile care traversează izvoare subterane şi cu 0 pe cele care nu traversează izvoare subterane.
Ne interesează să studiem traseele distincte care îndeplinesc simultan următoarele condiţii:
- un traseu trece pe la
M cabane exact o singură dată;
- între oricare două cabane consecutive pe traseu există potecă de legătură şi cel puţin una dintre aceste poteci traversează un izvor subteran;
- de la ultima cabană de pe traseu se poate reveni la cabana de plecare folosind o potecă.
Două trasee sunt considerate distincte dacă există cel puţin o poziţie
i (
1≤i≤M) astfel încât a
i-a cabană de pe primul traseu este diferită de a
i-a cabană de pe cel de-al doilea traseu.
Cerinţă
Cunoscând harta regiunii, să se determine numărul de trasee distincte care îndeplinesc condiţiile din enunţ.
Date de intrare
Fişierul de intrare
izvor.in va conţine pe prima linie numerele naturale
N P M, separate prin câte un singur spaţiu, având semnificaţia din enunţ. Pe următoarele
P linii sunt descrise cele
P poteci, câte o potecă pe o linie, sub forma a 3 numere naturale separate prin spaţii
x y z cu semnificaţia: ″există potecă între cabanele
x şi
y;
z este 1 dacă poteca trece peste un izvor subteran, respectiv 0, în caz contrar″.
Date de ieşire
Fişierul de ieşire
izvor.out va conţine o singură linie pe care va fi scris un număr natural ce reprezintă numărul de trasee distincte ce îndeplinesc condiţiile din enunţ.
Restricţii
4 ≤ N ≤ 20
3 ≤ P ≤ 100
3 ≤ M ≤ 7
Între oricare două cabane
x şi
y poate exista cel mult o potecă ce poate fi parcursă atât de la
x la
y, cât şi de la
y la
x.
Numărul de soluţii nu depăşeşte
1012.
Exemple
izvor.in | izvor.out | Explicaţii |
5 6 3
1 2 0
1 3 0
1 4 0
2 3 0
2 4 1
2 5 1
| 4
| Există 5 cabane şi 6 poteci, dintre care două traversează izvoare subterane.
Cele 4 trasee care îndeplinesc condiţiile din enunţ sunt:
1 2 4
1 4 2
2 4 1
4 2 1 |