g2mm

G2mm

== 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") ==

3243