== include(page="template/taskheader" task_id="puzzle2") ==

Ionita si Costi si-au cumparat un puzzle dreptunghiular cu oraşul Amsterdam, format din $N$ piese de aceeasi marime. Din pacate oricat s-au chinuit, nu au fost in stare sa il rezolve, asa ca i-au cerut ajutorul lui Alberto. Acesta nevrand sa le strice distractia de a rezolva puzzle s-a hotarat sa scrie pe spatele fiecarei piese un numar de la $1$ la $N$ si sa le dea o lista de $M$ perechi $(a{~i~}, b{~i~})$ lui Ionita si Costi cu semnificatia ca piesele numerotate cu $a{~i~}$ si cu $b{~i~}$ ar fi vecine daca puzzle-ul ar fi rezolvat corect.

Ionita si Costi si-au cumparat un puzzle dreptunghiular cu oraşul Amsterdam, format din $N$ piese de aceeasi marime. Din pacate oricat s-au chinuit, nu au fost in stare sa il rezolve, asa ca i-au cerut ajutorul lui Alberto. Acesta nevrand sa le strice distractia de a rezolva un puzzle s-a hotarat sa scrie pe spatele fiecarei piese un numar de la $1$ la $N$ si sa le dea o lista de $M$ perechi $(a{~i~}, b{~i~})$ lui Ionita si Costi cu semnificatia ca piesele numerotate cu $a{~i~}$ si cu $b{~i~}$ ar fi vecine (ar avea o latură în comun) daca puzzle-ul ar fi rezolvat corect.

Cei doi insa nici acum nu au reusit sa rezolve problema asa ca va roaga pe voi sa o faceti pentru ei. Ei va ofere cele $M$ perechi si va roaga sa reconstituiti puzzle-ul

Cei doi insa nici acum nu au reusit sa rezolve problema asa ca va roaga pe voi sa o faceti pentru ei. Ei vă oferă cele $M$ perechi si va roaga sa reconstituiti puzzle-ul.

h2. Date de intrare