Primăria oraşului ioliPest este alimentată cu electricitate prin intermediul unei reţele vechi de câteva zeci de ani, care are mari pierderi de putere pe linii. Reţeaua este alcătuită din noduri şi conexiuni între unele perechi de noduri. Structura reţelei este, însă, una specială, asemănătoare reţelelor de rezistenţe serie-paralel şi conţine două noduri speciale, numite nodul stânga şi nodul dreapta. Astfel, reţeaua are o structură ce corespunde unuia dintre următoarele 3 cazuri:
• 2 noduri unite printr-o conexiune (vom numi această structură “reţea de bază”); în figură, nodul stânga al acestei reţele este marcat cu T1, iar nodul dreapta cu T2;
• conectarea în serie a două reţele; considerând două reţele R1 şi R2, acestea se conectează în serie suprapunând nodul dreapta al lui R1 peste nodul stânga al lui R2; nodul stânga al reţelei rezultate este nodul stânga al lui R1, iar nodul dreapta al reţelei rezultate este nodul dreapta al lui R2;
• conectarea în paralel a două reţele; considerând două reţele R1 şi R2, acestea se conectează în paralel suprapunând nodul stânga al lui R1 peste nodul stânga al lui R2 şi nodul dreapta al lui R1 peste nodul dreapta al lui R2; nodul stânga al reţelei rezultate este dat de suprapunerea nodurilor stânga ale reţelelor R1 şi R2, iar nodul dreapta al reţelei rezultate este dat de suprapunerea nodurilor dreapta ale reţelelor R1 şi R2; în urma conectării în paralel pot rezulta conexiuni multiple între nodul stânga şi nodul dreapta al reţelei rezultate (de exemplu, în cazul conectării în paralel a două “reţele de bază”).
În vederea pregătirii integrării în Uniunea Europeană, s-au primit fonduri pentru schimbarea reţelei. Operaţia de schimbare a reţelei presupune, în prima etapă, eliminarea tuturor conexiunilor dintre nodurile reţelei (urmând ca, ulterior, aceste conexiuni să fie înlocuite cu unele mai performante). În urma calculelor efectuate, s-a ajuns la concluzia că cea mai eficientă metodă de eliminare a conexiunilor din cadrul reţelei este de a elimina unele noduri ale reţelei împreună cu toate conexiunile adiacente acestor noduri. Aşadar, trebuie eliminată o submulţime de noduri astfel încât orice conexiune a reţelei să aibă cel puţin unul dintre capete în această submulţime. Evident, se doreşte să se elimine un număr minim de noduri.
Cerinţă
Dându-se o reţea a cărei structură respectă regulile precizate mai sus, determinaţi numărul minim de noduri ce trebuie eliminate pentru ca, odată cu ele, să fie eliminate toate conexiunile existente în reţea.
Reţeaua este descrisă sub forma unui şir de caractere ce respectă următoarele reguli gramaticale:
Caracterul S reprezintă operaţia de conectare în serie a două reţele, iar caracterul P reprezintă operaţia de conectare în paralel a două reţele. Se observă că gramatica descrisă anterior este similară unei gramatici a expresiilor aritmetice, în care S şi P sunt operatori binari (se aplică asupra a două reţele). În urma acestei observaţii şi pentru a evita ambiguităţile ce ar putea fi produse de unele şiruri, vom considera că operatorul P are o prioritate mai mare decât operatorul S. Astfel, şirul BPBSB corespunde unei conectări în paralel a două “reţele de bază”, reţeaua rezultată fiind apoi conectată în serie cu o altă “reţea de bază” (şirul este echivalent cu (BPB)SB, unde existenţa parantezelor specifică clar ordinea de aplicare a operatorilor).
Cele două reţele descrise în figurile anterioare (în afara “reţelei de bază”) corespund următoarelor două şiruri: (BSBSB)P(BSB)S(BSB), respectiv (BSBSB)PB.
Date de intrare
Pe prima linie a fişierului de intrare rsp.in se află numărul întreg T, reprezentând numărul de reţele ce vor fi descrise în continuare. Următoarele T linii conţin câte un şir de caractere ce reprezintă descrierea corectă a câte unei reţele.
Date de ieşire
În fişierul rsp.out veţi afişa T linii, reprezentând numărul minim de noduri ce trebuie eliminate din fiecare reţea descrisă în fişierul de intrare. Primul număr afişat corespunde primei reţele descrise, al doilea număr celei de-a doua reţele descrise ş.a.m.d.
Restricţii
1 ≤ T ≤ 10
Orice şir din fişierul de intare va conţine cel mult 100000 de caractere.
Niciun şir din fişierul de intrare nu va conţine spaţii; şirurile sunt formate numai din caracterele B, S, P, ( şi ).
Orice linie din fişierul de intrare are la sfârşit caracterul “linie nouă”.
60% din fişierele de test vor conţine numai şiruri având lungimi ≤ 5000 de caractere.
Exemple
rsp.in
rsp.out
7
B
(BSBSB)P(BSB)S(BSB)
(BSBSB)PB
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)
