| Fişierul intrare/ieşire: | dep.in, dep.out | Sursă | ONI 2008 - baraj |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Pripoae Teodor Anton •toni2007 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dep
Zaharel vrea sa plece intr-o excursie impreuna cu K dintre cei N prieteni (numerotati de la 1 la N) ai sai. Desigur, nu poate lua cu el orice grup de K prieteni, deoarece prezenta anumitor prieteni este conditionata de prezenta altora. Fiind un bun cunoscator al interactiunilor sociale din cadrul grupului sau de prieteni, Zaharel a facut o lista cu toate cele M dependente existente in grupul sau: perechi de numere i j cu semnificatia ca prietenul cu numarul i va veni in excursie, doar daca prietenul cu numarul j vine si el. Vom numi o astfel de relatie dependenta directa.
Vom spune in continuare ca doi prieteni i j sunt in dependenta indirecta daca sunt in dependenta directa sau daca exista un sir de T≥1 numere v1, v2, ... , vT, astfel incat i depinde direct de v1, vp depinde direct de vp+1 (pentru 1≤ p≤ T) si vT depinde direct de j.
La o analiza atenta a celor M relatii Zaharel a observat ca exista o proprietate interesanta in cadrul grupului sau: pentru oricare trei prieteni distincti cu numere i j k, daca i depinde indirect de j si i depinde indirect de k, atunci j depinde indirect de k, sau k depinde indirect de j, sau ambele.
Cerinta
Sa se scrie un program care determina in cate moduri poate alege Zaharel K dintre cei N prieteni ai lui pentru a merge in excursie, tinand cont de cele M relatii de dependenta.
Date de intrare
Fisierul de intrare dep.in va contine pe prima linie numerele N M K. Urmatoarele M linii vor contine perechi de numere i j reprezentand dependentele directe.
Date de iesire
Fisierul de iesire dep.out va contine pe prima linie un singur numar reprezentand in cate moduri poate alege Zaharel K dintre cei N prieteni. Rezultatul se va afisa modulo 666013.
Restrictii
- 1 ≤ K ≤ N ≤ 256
- 0 ≤ M ≤ N*(N-1)/2
- Pentru 20% din teste N ≤ 25
- Pentru 40% din teste nu vor exista dependente indirecte ciclice ( i depinde indirect de i)
Exemplu
| dep.in | dep.out |
|---|---|
| 5 8 3 1 2 2 1 1 3 2 3 4 5 5 4 4 3 5 3 | 2 |
Explicatie
Zaharel poate merge excursie fie cu prietenii 1 2 3, fie cu prietenii 3 4 5.
