| Fişierul intrare/ieşire: | g2mm.in, g2mm.out | Sursă | Selectie echipe ACM ICPC, UPB 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
G2mm
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, distG(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 G2) se defineste in felul urmator:
- are aceleasi noduri ca si graful G
- are muchie intre doua noduri x si y, numai daca distG(x,y) ≤ 2 (distanta dintre nodurile x si y este cel mult 2, in graful G)
Determinati, daca exista, un cuplaj perfect in G2. 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.
Date de intrare
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.
Date de iesire
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.
Restrictii
- 1 ≤ N ≤ 30.000, N par
- N-1 ≤ M ≤ 200.000
Exemplu
| g2mm.in | g2mm.out |
|---|---|
| 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 |
