Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | jimmy.in, jimmy.out | Sursă | Selectie echipe ACM ICPC, UPB 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Jimmy
Jimmy studiaza la universitate Algoritmi Avansati pe Grafuri. Ultima sa tema consta in gasirea unui cuplaj maxim intr-un tip special de graf. Acest graf este neorientat, are N noduri, iar fiecare nod are gradul 3. Mai mult, graful este biconex din punct de vedere al muchiilor (adica trebuie eliminate cel putin 2 muchii pentru ca graful sa nu mai fie conex). Un cuplaj este o submultime a muchiilor grafului, astfel incat oricare 2 muchii din submultime nu au nici un capat comun. Un cuplaj maxim este un cuplaj avand cardinal maxima.
Fiind date o serie de grafuri speciale avand proprietatile precizate mai sus, gasiti cardinalul unui cuplaj maxim pentru fiecare graf.
Date de intrare
Prima linie a fisierului de intrare jimmy.in contine numarul intreg T, reprezentand numarul de grafuri descrise in continuare. Descrierea fiecarui graf contine pe prima linie numarul intreg par N, reprezentand numarul de noduri ale grafului. Fiecare din urmatoarele 3*N/2 linii contine cate 2 numere intregi, A si B, separate printr-un spatiu, avand semnificatia ca exista o muchie intre nodul A si nodul B. Nodurile sunt numerotate de la 1 la N.
Date de iesire
Pentru fiecare din cele T grafuri date in fisierul de intrare, afisati in fisierul de iesire jimmy.out cate o linie continand cardinalul unui cuplaj maxim.
Restrictii
- 1 ≤ T ≤ 50
- 4 ≤ N ≤ 5000
Exemplu
| jimmy.in | jimmy.out |
|---|---|
| 2 4 1 2 1 3 1 4 2 3 2 4 3 4 4 1 2 1 3 1 4 2 3 2 4 3 4 | 2 2 |
