Fişierul intrare/ieşire:dep.in, dep.outSursăONI 2008 - baraj
AutorMircea Bogdan PasoiAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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≤ pT) 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

  • 1KN256
  • 0MN*(N-1)/2
  • Pentru 20% din teste N25
  • Pentru 40% din teste nu vor exista dependente indirecte ciclice ( i depinde indirect de i)

Exemplu

dep.indep.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content