== include(page="template/taskheader" task_id="g2mm") ==
Poveste si cerinta...
Se da un graf conex si neorientat $G$, avand $N$ noduri si $M$ muchii. Distanta dintre doua noduri $x$ si $y$ ale unui graf $G$, $dist{~G~}(x,y)$ se defineste ca fiind numarul minim de muchii ce trebuie traversate pentru a ajunge de la un nod la celalalt. Patratul unui graf $G$ (notat cu $G^2^$) se defineste in felul urmator:
* are aceleasi noduri ca si graful $G$
* are muchie intre doua noduri $x$ si $y$, numai daca $dist{~G~}(x,y) ≤ 2$ (distanta dintre nodurile $x$ si $y$ este cel mult $2$, in graful $G$)
Determinati, daca exista, un cuplaj perfect in $G^2^$. Un cuplaj perfect intr-un graf $H$ consta din $N/2$ muchii, astfel incat fiecare din cele $N$ noduri ale lui $H$ apare ca unul din cele $2$ capete ale exact unei singure muchii din cadrul cuplajului.
h2. Date de intrare
Fisierul de intrare $g2mm.in$ ...
Prima linie a fisierului de intrare $g2mm.in$ contine numerele intregi $N$ si $M$, separate printr-un spatiu. Urmatoarele $M$ linii contin cate $2$ numere intregi $x$ si $y$, separate printr-un spatiu, reprezentand doua noduri din graf care sunt conectate printr-o muchie. Nodurile grafului sunt numerotate de la $1$ la $N$.
h2. Date de iesire
In fisierul de iesire $g2mm.out$ ...
Prima linie a fisierului de iesire $g2mm.out$ va contine numarul intreg $A$, avand valoarea $1$, daca exista un cuplaj perfect in patratul grafului dat, sau $0$, in caz contrar. Daca $A=1$, atunci urmatoarele $N/2$ linii vor contine cate $2$ numere intregi $x$ si $y$, descriind cate o muchie a cuplajului perfect gasit.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 30.000$, $N$ par
* $N-1 ≤ M ≤ 200.000$
h2. Exemplu
table(example). |_. g2mm.in |_. g2mm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|8 11
1 3
2 3
3 5
5 4
4 8
8 6
6 1
7 8
7 6
3 7
5 6
|1
5 4
6 8
2 7
1 3
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="g2mm") ==
