java

Gandaci Java

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

==Include(page="template/taskheader" task_id="java")==

Poveste ...

==Include(page="template/raw")==

h2. Cerinta

Pe insula Java, se fac experimente crude pe unele dintre cele mai frumoase creaturi din lume, gandacii. $M$ cercetatori fac experimente pe $N$ gandaci. Din pacate, dupa ce au alcatuit un plan inteligent, toti gandacii au scapat din laborator si au fugit in parti diferite ale insulei. Cercetatorii trebuie sa aduca gandacii inapoi pentru a continua experimentele. Pentru a face asta, fiecare cercetator este trimis sa caute cel mult un gandac. Gandacii sunt numerotati cu numere de la $1$ la $N$. Cercetatori poarte ecusoane cu numere de la $1$ la $M$. Un cercetator poate cauta un gandac doar daca a facut vreodata un experiment pe acel gandac (altfel, nu ar putea sa-l recunoasca).

...
 
h2. Restrictii
 
...

Cunoscandu-se experimentele care au avut loc inainte sa scape gandacii, sa se determine care este numarul maxim de gandaci care pot fi adusi inapoi in laborator dupa o cantitate finita de timp. Se stie ca, daca un cercetator este trimis in cautarea unui gandac, il va gasi intr-o cantitate finita de timp (pentru ca ar fi imposibil pentru un gandac Java sa fie mai destept decat un cercetator).

h2. Date de intrare

...

Prima linie din fisierul $java.in$ contine numarul natural $T$, reprezentand numarul de teste. In continuare, se vor descrie cele $T$ teste. Prima linie a fiecarui test contine trei numere naturale: $M$, $N$ si $E$. $M$ este numarul de cercetatori, $N$ este numarul de gandaci si $E$ este numarul de experimente care au avut loc. Urmatoarele $E$ linii contin cate doua numere naturale $A$ si $B$, cu semnificatia ca cercetatorul $A$ a facut un experiment pe gandacul $B$. Un cercetator poate face mai multe experimente pe acelasi gandac.

h2. Date de iesire

...

Pentru fiecare test afisati cate o linie in fisierul $java.out$ continand un numar natural: numarul maxim de gandaci care pot fi adusi inapoi la laborator dupa o cantitate finita de timp.
 
h2. Restrictii
 
* $1 ≤ T ≤ 6$
* $1 ≤ N, M ≤ 10.000$
* $0 ≤ E ≤ 200.000$

h2. Exemplu

| java.in | java.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. java.in |_. java.out |
| 2
4 5 2
1 2
1 2
3 3 5
1 1
1 2
2 2
2 3
3 3
| 1
3 |
 

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

==Include(page="template/taskfooter" task_id="java")==