== include(page="template/taskheader" task_id="intensitate") ==
Giugudel, sătul de atâtea reparaţii la panouri electrice, a hotărât sa îşi diversifice activitarea, şi a găsit de cuviinţă să meargă la teatru. Zis şi făcut - şi-a luat bilete, a aşteptat cu nerăbdare ziua spectacolului, însă cum a a ajuns la teatru a aflat cu neplăcere ca generatorul de curent s-a stricat, şi deci reprezentaţia trebuia amânată. Fiind singurul care putea face ceva, şi nedorind să se dea bătut cu una cu două, el s-a angajat fată de conducerea teatrului sa foloseasca generatorul de curent auxiliar pentru a reporni un număr minim de becuri astfel încât să se poată vedea pe scenă.
Giugudel, sătul de atâtea reparaţii la panouri electrice, a hotărât sa îşi diversifice activitarea, şi a găsit de cuviinţă să meargă la teatru. Zis şi făcut: şi-a luat bilete, a aşteptat cu nerăbdare ziua spectacolului, însă cum a a ajuns la teatru a aflat cu neplăcere ca generatorul de curent s-a stricat, şi deci reprezentaţia trebuia amânată. Fiind singurul care putea face ceva, şi nedorind să se dea bătut cu una cu două, el s-a angajat faţă de conducerea teatrului să folosească generatorul de curent auxiliar pentru a reporni un număr minim de becuri astfel încât să se poată vedea pe scenă.
Se ştie că reţeaua electrică a teatrului formată din $N$ becuri poate fi codificată sub forma unui circuit definit în mod recursiv:
* Dacă $C$ este un circuit atunci $A-C-B$ este un circuit, unde $A$ şi $B$ sunt becuri. Acest lucru inseamnă că $A$, $C$ şi $B$ sunt grupate in **serie**. Vezi figura de mai jos pentru detalii.
!problema/intensitate?serie.jpeg 90%!
* Daca $C{~1~},C{~2~}..C{~x~}$ sunt circute şi $A$, $B$ sunt becuri, atunci $A-{C{~1~},C{~2~}..C{~x~}}-B$ este un circuit. În acest caz vom spune că circuitele $C{~1~},C{~2~}..C{~x~}$ sunt grupate în **paralel**. Mai mult, $x$ va fi **cel mult $7$**. Vezi figura de mai jos pentru detalii.
* Daca $C{~1~},C{~2~}..C{~x~}$ sunt circute şi $A$, $B$ sunt becuri, atunci $A-{C{~1~},C{~2~}..C{~x~}}-B$ este un circuit. În acest caz vom spune că circuitele $C{~1~},C{~2~}..C{~x~}$ sunt grupate în **paralel**. Vezi figura de mai jos pentru detalii.
!problema/intensitate?paralel.jpeg 90%!
Prin **$I$** ne referim la intensitatea curentului electric. În cazul circuitelor in serie, $I$ rămâne constant, iar în cazul circuitelor in paralel, $I$ se va divide la numarul de circuite aflate în paralel **pe care le folosim**. Pentru un bec oarecare <tex> \sum_{i=1}^{x} I_{in} = I = \sum_{i=1}^{x} I_{out} </tex>
Prin **$I$** ne referim la intensitatea curentului electric. În cazul circuitelor in serie, $I$ rămâne constant, iar în cazul circuitelor in paralel, $I$ se va divide la numarul de circuite aflate în paralel **pe care le folosim**. Pentru un bec oarecare <tex> \sum_{i=1}^{x} I_{in} = \sum_{i=1}^{x} I_{out} </tex>
Cu cât intensitatea curentului electric ce trece printr-un bec va fi mai mare, becul va lumina mai puternic.
Considerăm un bec ca fiind **pornit** dacă există un drum de la $1$ la $N$ care trece prin acel bec, şi toate becurile de pe drum sunt pornite (intensitatea curentului electric este strict pozitivă). Dacă nu există un astfel de drum, atunci becul nu va lumina. Considerăm direcţia curentului electric de la stânga spre dreapta.
Considerăm un bec ca fiind **pornit** dacă există un drum de la $1$ la $N$ care trece prin acel bec, şi toate becurile de pe drum sunt pornite (intensitatea curentului electric este strict pozitivă). Dacă nu există o astfel de rută, atunci becul nu va lumina.
Instalaţia având foarte multe becuri, şi Giugudel având foarte puţin timp la dispoziţie, vă roagă sa-l ajutaţi pentru a putea reporni reţeaua la timp. Mai mult, el doreşte ca toate becurile pornite să luminize cât mai tare.
Instalaţia având foarte multe becuri, şi Giugudel având foarte puţin timp la dispoziţie, vă roagă sa-l ajutaţi pentru a putea reporni reţeaua cât mai curând. Mai mult, el doreşte ca fiecare bec să luminize cât mai tare, adică valoarea minimă a intensităţii curentului electric ce va trece prin orice bec pornit să fie maximă.
h2. Cerinţă
Dându-se un circuit electric definit mai sus, trebuie sa găsiţi maximul pentru intensitatea curentului ce va trece printr-un bec, ştiind că trebuie repornite cel puţin $K$ becuri!
Dându-se un circuit definit mai sus, trebuie să găsiţi valoarea minimă maximizată a intensităţii curentului electric ce va trece printr-un bec pornit, ştiind că trebuie repornite cel puţin $K$ becuri!
h2. Date de intrare
Pe prima linie a fişierului de intrare $intensitate.in$ se află trei numere $N,K$ şi $M$ reprezentând numărul total de becuri, numărul minim de becuri ce trebuie aprinse şi numarul de legaturi între becuri.
Următoarele $M$ linii conţin câte o pereche $(x,y)$ cu semnificaţia că becul $x$ se învecinează cu becul $y$, becul $x$ fiind la stânga becului $y$.
Pe prima linie a fişierului de intrare $intensitate.in$ se află trei numere $N,K$ şi $M$ reprezentând numărul total de becuri, numărul minim de becuri ce trebuie aprinse şi numarul de legaturi între becuri. Următoarele $M$ linii conţin câte o pereche $(x,y)$ cu semnificaţia că becul $x$ se învecinează cu becul $y$, becul $x$ fiind la stânga becului $y$.
h2. Date de ieşire
Fişierul de ieşire $intensitate.out$ va conţine pe o singura linie două numere naturale $(p,q)$, soluţia fiind determinată de fracţia $p/q$.
Fişierul de ieşire $intensitate.out$ va conţine pe o singura linie două numere naturale $(p,q)$, soluţia fiind determinată de fracţia $p/q$, cu $p$ şi $q$ prime între ele.
h2. Restricţii
* $1 ≤ K ≤ N ≤ 100$
* $1 ≤ M ≤ 2 * N$
* Considerăm intensitatea curentului electric ce intră în becul $1$ din generator ca fiind **$1$**
* **Numărul maxim** de subcircuite puse în paralel va fi $7$
* Pentru $30%$ din teste $N ≤ 30$
* Pentru $70%$ din teste numărul maxim $x$ de subcircuite puse in paralel va fi $7$
* Se garantează că p şi q vor fi **întregi cu semn** pe $32$ biţi
* Considerăm intensitatea curentului electric ce intră în becul $1$ din generator ca fiind de valoare **$1$**
* Direcţia curentului electric este de la **stânga spre dreapta**
* Circuitul din fisierul de intrare va fi întotdeauna valid
h2. Exemplu
h3. Explicaţie
În primul caz, curentul electric va urma ruta $1-4-5-6$, iar becurile $2$ şi $3$ nu vor fi aprinse. În concluzie $1-4-5-6$ vor fi legate în serie, intensitatea curentului electric nemodificându-se.
Pe cel de-al doilea exemplu, este necesară adăugarea înca unui bec la configuraţia precedenta, fie acesta $2$. Becul $2$ este legat în paralel cu becurile $(4,5)$, deci intensitatea curentului electric ce intră în becul $2$ şi în becul $4$ este $1/2$.
Pe cel de-al doilea exemplu, este necesară adăugarea înca unui bec la configuraţia precedenta, fie acesta $2$. Becul $2$ este legat în paralel cu becurile $(4,5)$, deci intensitatea curentului electric ce intră în becul $2$ şi în becul $4$ este $1/2$. Observăm că dacă am fi ales şi becul $3$, atunci intensitatea minimă a curentului electric ce ar trece prin circuit nu ar mai fi avut valoare maximă, fiind egală cu $1/3$.
== include(page="template/taskfooter" task_id="intensitate") ==
