Fişierul intrare/ieşire:	colonii.in, colonii.out	Sursă	ACM ICPC Faza Nationala 2015
Autor	Florin Pop	Adăugată de	Comisie ICPC UPB •neapuiu
Timp execuţie pe test	1.15 sec	Limită de memorie	66048 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Colonii

Î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₁ depinde de o altă colonie C₂, dacă şi numai dacă toate căile de transport existente, de la colonia producătoare de motoare la colonia C₁, trec prin C₂.
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.

Date de intrare

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

Date de ieşire

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

Restricţii

• 1 ≤ N, C ≤ 5.000
• 1 ≤ M ≤ 650.000

Exemplu

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.

Cum se trimit solutii?