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

==Include(page="template/taskheader" task_id="java")==
 
 
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$. Cercetatorii poarta 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).
 
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
 
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/raw")==
 
Gandaci Java
 
 
 
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).
 
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
 
S 1 <= T <= 6
 
S 1 <= N, M <= 10,000
 
S 0 <= E <= 200,000
 
h2. Exemplu
 
java.in java.out
2 1
 
4 5 2 3
 
1 2
 
1 2
 
3 3 5
 
1 1
 
1 2
 
2 2
 
2 3
 
3 3
 
 
==Include(page="template/taskfooter" task_id="java")==

1324