Fişierul intrare/ieşire:java.in, java.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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. 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).

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.

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.

Restrictii

  • 1 ≤ T ≤ 6
  • 1 ≤ N, M ≤ 10.000
  • 0 ≤ E ≤ 200.000

Exemplu

java.injava.out
2
4 5 2
1 2
1 2
3 3 5
1 1
1 2
2 2
2 3
3 3
1
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content