Fişierul intrare/ieşire:colonii.in, colonii.outSursăACM ICPC Faza Nationala 2015
AutorFlorin PopAdăugată deneapuiuComisie ICPC UPB neapuiu
Timp execuţie pe test2.3 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/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 C1 depinde de o altă colonie C2, dacă şi numai dacă toate căile de transport existente, de la colonia producătoare de motoare la colonia C1, trec prin C2.
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

colonii.incolonii.out
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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?