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

Poveste si cerinta...

Primaria orasului ioliPest este alimentata cu electricitate prin intermediul unei retele vechi de cateva zeci de ani, care are mari pierderi de putere pe linii. Reteaua este alcatuită din noduri si conexiuni intre unele perechi de noduri. Structura retelei este, insa, una speciala, asemanatoare retelelor de rezistente serie-paralel si contine doua noduri speciale, numite nodul stanga si nodul dreapta. Astfel, reteaua are o structura ce corespunde unuia dintre urmatoarele 3 cazuri:
 
* 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~}$;
 
* conectarea in serie a doua retele; considerand doua retele $R{~1~}$ ÅŸi $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~}$;
 
* 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").
 
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.
 
Reteaua este descrisa sub forma unui sir de caractere ce respecta urmatoarele reguli gramaticale:
 
Reţea de bază	=	B
Reţea	=	Reţea de bază
sau
Reţea S Reţea
sau
Reţea P Reţea
sau
( Reţea )
 
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 două 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