Fişierul intrare/ieşire:	puzzle2.in, puzzle2.out	Sursă	ONIS 2016 Runda Online
Autor	Adrian Budau	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 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 vă oferă cele M perechi si va roaga sa reconstituiti puzzle-ul.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 400.000
• 1 ≤ a_i, b_i ≤ N
• 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.

Exemplu

Cum se trimit solutii?