dep

Dep

== include(page="template/taskheader" task_id="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$, dac� $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.

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 $v{~1~}$, $v{~2~}$, ... , $v{~T~}$, astfel incat $i$ depinde direct de $v{~1~}$, $v{~p~}$ depinde direct de $v{~p+1~}$ (pentru 1≤ $p$≤ $T$) si $v{~T~}$ 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.

h2. Cerinta

h2. Date de iesire

Fisierul de iesire $dep.out$ va contine pe prima linie un singur numar reprezentand în cate moduri poate alege Zaharel $K$ dintre cei $N$ prieteni. Rezultatul se va afisa modulo $666013$.

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$.

h2. Restrictii

h3. Explicatie

Zahrel poate merge excursie fie cu prietenii 1 2 3, fie cu prietenii 3 4 5.

Zaharel poate merge excursie fie cu prietenii 1 2 3, fie cu prietenii 3 4 5.

!problema/dep?graf.jpg!

3087