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
1 4
2 5
2 3
2 4
4 5
1 2
2 4
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.