== include(page="template/taskheader" task_id="colonii") ==
Poveste şi cerinţă...
În galaxia noastră există o singură colonie producătoare de motoare super-luminice (care deţine şi secretul acestor motoare), iar livrarea acestora către alte colonii din alte galaxii se face într-un singur sens (motoarele nu se returneaza), dar nu direct, ci prin colonii intermediare (astfel motoarele sunt protejate de drumuri lungi).
O colonie $C{~1~}$ depinde de o altă colonie $C{~2~}$, dacă şi numai dacă toate căile de transport existente, de la colonia producătoare de motoare la colonia $C{~1~}$, trec prin $C{~2~}$.
Scrieţi un program care să determine pentru fiecare colonie care este numărul de colonii de care depinde din punct de vedere al transportului de motoare.
h2. Date de intrare
Fişierul de intrare $colonii.in$ ...
Fişierul de intrare $colonii.in$ conţine pe prima linie 3 numere întregi separate prin câte un spaţiu $N$, $M$ si $C$, cu semnificaţia: $N$ - numărul de colonii, $M$ - numărul de legături de transport şi $C$ - colonia producătoare de motoare. Coloniile vor fi identificate prin numere naturale distincte de la $1$ la $N$. Fiecare dintre următoarele $M$ linii va conţine două numere întregi $x$ si $y$, separate printr-un spaţiu, cu semnificaţia “există o legătură unidirectionala de la colonia $x$ la colonia $y$ ”.
h2. Date de ieşire
În fişierul de ieşire $colonii.out$ ...
În fişierul de ieşire $colonii.out$ va conţine $N$ linii, câte una pentru fiecare colonie. Pe linia $i$ din fişierul de ieşire se va tipări numărul de colonii de care depinde colonia $i$, din punct de vedere al transportului de motoare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, C ≤ 5.000$
* $1 ≤ M ≤ 650.000$
h2. Exemplu
table(example). |_. colonii.in |_. colonii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 9 3
1 2
1 5
2 3
2 4
3 1
3 2
4 1
4 2
5 2
| 1
1
0
2
2
|
h3. Explicaţie
...
Colonia 1 depinde de colonia 3.
Colonia 2 depinde de colonia 3.
Colonia 3 nu depinde de nimeni.
Colonia 4 depinde de colonia 3 şi de colonia 2.
Colonia 5 depinde de colonia 3 şi de colonia 1.
== include(page="template/taskfooter" task_id="colonii") ==
