jimmy

Jimmy

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

Poveste si cerinta...

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 maximal.
Fiind date o serie de grafuri speciale avand proprietatile precizate mai sus, gasiti cardinalul unui cuplaj maxim pentru fiecare graf.

h2. 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$.

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

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 50$
* $4 ≤ N ≤ 5000$

h2. Exemplu
table(example). |_. jimmy.in |_. jimmy.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|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

|

h3. Explicatie

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

...
== include(page="template/taskfooter" task_id="jimmy") ==

2184