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

Poveste şi cerinţă...

Ionita si Costi si-au cumparat un puzzle cu Amsterdam-ul, format din $N$ piese. Din pacate ori cat 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.
 
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

h2. Date de intrare

Fişierul de intrare $puzzle2.in$ ...

Fişierul de intrare $puzzle2.in$ va contine pe prima linia $N$ si $M$ reprezentand numarul de piese de puzzle, respectiv de perechi.
 
Urmatoarele $M$ linii vor contine $2$ numere separate printr-un spatiu: $(a{~i~}, b{~i~})$.

h2. Date de ieşire

În fişierul de ieşire $puzzle2.out$ ...

În fişierul de ieşire $puzzle2.out$ trebuie sa contina pe prima linie $2$ numere $R$ si $C$, reprezentand numarul de linii, respectiv de coloane din puzzle.
 
Urmatoarele $R$ linii trebuie sa contina $C$ numere fiecare, intre $1$ si $N$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 400.000$
* $1 ≤ a{~i~}, b{~i~} ≤ N$
* $1 a{~i~} ≠ b{~i~}$
* $Cele M perechi reprezinta toate perechile posibile din puzzle. Daca puzzle-ul are R randuri si C coloane atunci M = (R - 1) * C + (C - 1) * R$
* $Se garanteaza existenta unei solutii.$
* $Se accepta orice solutie corecta.$

h2. Exemplu
table(example). |_. puzzle2.in |_. puzzle2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 9 12
1 9
5 4
8 9
7 3
1 7
3 5
6 5
8 2
9 3
7 4
3 2
6 2
| 3 3
2 4 8
3 5 9
6 7 1

|
h3. Explicaţie