jimmy

Jimmy

== include(page="template/taskheader" task_id="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 avadn cardinalitate maxima.
Fiind date o serie de grafuri speciale avand proprietatile precizate mai sus, gasiti cardinalitatea unui cuplaj maxim pentru fiecare graf.

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

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 cardinalitate unui cuplaj maxim.

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

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

2184