cadere
Drumurile dintre orasele din Imperiul Roman stau la baza dezvoltarii rapide a imperiului. De acest lucru si-au dat seama si inamicii imperiului care au īnceput sa le distruga.
Inainte de a se lua masuri se doreste monitorizarea pagubelor provocate de aceste distrugeri. Unul dintre cei mai importanti factori este distanta fata de capitala. Aceasta este numarul minim de drumuri ce trebuie parcurse pentru a ajunge īn/din capitala (drumurile sunt bidirectionale, iar lungimea lor nu conteaza).
Cerinta
Date fiind drumurile dintre orase si ordinea īn care acestea sunt distruse, evaluati numarul de orase
care s-au departat cu cel putin o unitate dupa distrugerea fiecarui drum.
Orasele care nu mai au nici o legatura cu capitala se considera la distanta infinit.
Date de intrare
Fisierul de intrare cadere.in
contine pe prima linie patru numere naturale nenule N,
M, C
si Q, reprezentānd numarul de
orase, numarul de drumuri initiale, capitala si respectiv numarul de drumuri
ce urmeaza a fi distruse.
Pe urmatoarele M linii se afla
cāte 2 numere naturale: O1
si O2, reprezentānd un drum īntre
orasele O1 si O2.
Orasele sunt numerotate de la 1
la N.
Pe urmatoarele Q linii se afla,
in ordine, drumurile ce urmeaza sa fie distruse. Pe fiecare dintre cele Q
linii sunt scrise doua numere naturale O1
O2, reprezentānd orasele care sunt capetele unui drum (drum aflat in
multimea drumurilor de mai sus).
Numerele de
pe aceeasi linie sunt separate prin spatii.
Date de iesire
Fisierul de iesire cadere.out
va contine Q linii. Pe linia
i va fi scris numarul de orase
ce s-au mai departat de capitala cu cel putin o unitate dupa distrugerea celui
de-al i-lea drum din fisierul
de intrare.
Restrictii si
precizari
1 <= N <= 1 000
1 <= M <= 50 000
1 <= Q <= M
Intre oricare doua orase exista cel mult un drum.
Un drum odata distrus nu se mai poate distruge din nou.
Exemplu
| cadere.in | cadere.out | Explicatii |
|
5 6 2 2 |
1 2 |
Dupa distrugerea drumului (1,2)
orasul 1 se departeaza cu
o unitate de capitala (orasul 2). Dupa distrugerea drumului (2,4) orasele 1 si 4 se departeaza cu cāte o unitate. |
Timp maxim de executie/test:
1.5 secunde
Memorie totala
disponibila 20 MB, din care 1 MB pentru stiva.
Marius Andrei
Google Inc
marsamg@yahoo.com