== 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 avand cardinal maxima.

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

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

2184