rsp

Rsp

* 2 noduri unite printr-o conexiune (vom numi aceasta structura "retea de baza"); in figura, nodul stanga al acestei retele este marcat cu $T{~1~}$, iar nodul dreapta cu $T{~2~}$;

!problema/rsp?1.bmp!
 

* conectarea in serie a doua retele; considerand doua retele $R{~1~}$ si $R{~2~}$, acestea se conecteaza in serie suprapunand nodul dreapta al lui $R{~1~}$ peste nodul stanga al lui $R{~2~}$; nodul stanga al retelei rezultate este nodul stanga al lui $R{~1~}$, iar nodul dreapta al retelei rezultate este nodul dreapta al lui $R{~2~}$;

!problema/rsp?2.bmp!
 

* conectarea in paralel a doua retele; considerand doua retele $R{~1~}$ si $R{~2~}$, acestea se conecteaza in paralel suprapunand nodul stanga al lui R{~1~} peste nodul stanga al lui $R{~2~}$ si nodul dreapta al lui $R{~1~}$ peste nodul dreapta al lui $R{~2~}$; nodul stanga al retelei rezultate este dat de suprapunerea nodurilor stanga ale retelelor $R{~1~}$ si $R{~2~}$, iar nodul dreapta al retelei rezultate este dat de suprapunerea nodurilor dreapta ale retelelor $R{~1~}$ si $R{~2~}$; in urma conectarii in paralel pot rezulta conexiuni multiple intre nodul stanga si nodul dreapta al retelei rezultate (de exemplu, in cazul conectarii in paralel a doua "retele de baza").

!problema/rsp?3.bmp!
 

In vederea pregatirii integrarii in Uniunea Europeana, s-au primit fonduri pentru schimbarea retelei. Operatia de schimbare a retelei presupune, in prima etapa, eliminarea tuturor conexiunilor dintre nodurile retelei (urmand ca, ulterior, aceste conexiuni sa fie inlocuite cu unele mai performante). In urma calculelor efectuate, s-a ajuns la concluzia ca cea mai eficienta metoda de eliminare a conexiunilor din cadrul retelei este de a elimina unele noduri ale retelei impreuna cu toate conexiunile adiacente acestor noduri. Asadar, trebuie eliminata o submultime de noduri astfel incat orice conexiune a retelei sa aiba cel putin unul dintre capete in aceasta submultime. Evident, se doreste sa se elimine un numar minim de noduri.
Dandu-se o retea a carei structura respecta regulile precizate mai sus, determinati numarul minim de noduri ce trebuie eliminate pentru ca, odata cu ele, sa fie eliminate toate conexiunile existente in retea.

sau
(@Retea@) |

Caracterul $S$ reprezinta operatia de conectare in serie a doua retele, iar caracterul $P$ reprezinta operatia de conectare in paralel a doua retele. Se observa ca gramatica descrisa anterior este similara unei gramatici a expresiilor aritmetice, in care $S$ si $P$ sunt operatori binari (se aplica asupra a doua retele). In urma acestei observatii si pentru a evita ambiguitatile ce ar putea fi produse de unele siruri, vom considera ca operatorul $P$ are o prioritate mai mare decat operatorul $S$. Astfel, sirul $BPBSB$ corespunde unei conectari in paralel a doua "retele de baza", reteaua rezultata fiind apoi conectata in serie cu o alta "retea de baza" (sirul este echivalent cu $(BPB)SB$, unde existenta parantezelor specifica clar ordinea de aplicare a operatorilor).
Cele doua retele descrise in figurile anterioare (in afara "retelei de baza") corespund urmatoarelor doua siruri: $(BSBSB)P(BSB)S(BSB)$, respectiv $(BSBSB)PB$.

Caracterul $S$ reprezinta operatia de conectare in serie a doua retele, iar caracterul $P$ reprezinta operatia de conectare in paralel a doua retele. Se observa ca gramatica descrisa anterior este similara unei gramatici a expresiilor aritmetice, in care $S$ si $P$ sunt operatori binari (se aplica asupra a doua retele). In urma acestei observatii si pentru a evita ambiguitatile ce ar putea fi produse de unele siruri, vom considera ca operatorul $P$ are o prioritate mai mare decat operatorul $S$. Astfel, sirul $BPBSB$ corespunde unei conectari in paralel a doua "retele de baza", reteaua rezultata fiind apoi conectata in serie cu o alta "retea de baza" (sirul este echivalent cu @(BPB)SB@, unde existenta parantezelor specifica clar ordinea de aplicare a operatorilor).
Cele doua retele descrise in figurile anterioare (in afara "retelei de baza") corespund urmatoarelor doua siruri: @(BSBSB)P(BSB)S(BSB)@, respectiv @(BSBSB)PB@.

h2. Date de intrare

h2. Date de iesire

In fiÅŸierul de iesire veti afisa $T$ linii, reprezentand numarul minim de noduri ce trebuie eliminate din fiecare retea descrisa in fisierul de intrare. Primul numar afisat corespunde primei retele descrise, al doilea numar celei de-a doua retele descrise s.a.m.d.

In fisierul de iesire veti afisa $T$ linii, reprezentand numarul minim de noduri ce trebuie eliminate din fiecare retea descrisa in fisierul de intrare. Primul numar afisat corespunde primei retele descrise, al doilea numar celei de-a doua retele descrise s.a.m.d.

h2. Restrictii si precizari

* $1 &le T ≤ 10$
* Orice sir din fiÅŸierul de intare va contine cel mult $100000$ de caractere.

* $1 ≤ T ≤ 10$
* Orice sir din fisierul de intare va contine cel mult $100000$ de caractere.

* Nici un sir din fisierul de intrare nu va contine spatii; sirurile sunt formate numai din caracterele $B$, $S$, $P$, $($ si $)$.
* Orice linie din fisierul de intrare are la sfarsit caracterul "linie noua".
* $60%$ din fisierele de test vor contine numai siruri avand lungimi ≤ $5000$ de caractere.

BPBPBPBPBPBPBPBPBPB
(BSB)P(BSB)P(BSB)P(BSB)P(BSB)
(BSBSB)P(BSBSB)P(BSBSB)P(BSBSB)P(BSBSB)

BPBSBPBP(BSB)S(BSBSB)P(BSBPB)

@BPBSBPBP(BSB)S(BSBSB)P(BSBPB)@

| 1
4
2

== include(page="template/taskfooter" task_id="rsp") ==

1634