Fişierul intrare/ieşire:puzzle2.in, puzzle2.outSursăONIS 2016 Runda Online
AutorAdrian BudauAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 (ai, bi) lui Ionita si Costi cu semnificatia ca piesele numerotate cu ai si cu bi 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: ai, bi.

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 ≤ ai, bi ≤ N
  • ai ≠ bi
  • 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

puzzle2.inpuzzle2.out
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
4 5 6
7 3 2
1 9 8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?