Taurinei îi place foarte mult să taie. În special grafuri neorientate. Îţi aminteşti încă de la cursurile de algoritmi şi structuri de date că o tăietură într-un graf este o **partiţie a mulţimii de noduri în două submulţimi nevide**. Îţi dai seama că de îndată ce i-l vei oferi, Taurina va începe să taie graful în toate modurile posibile şi să se minuneze de ce va obţine. Cum eşti un frate bun şi Taurina este o surioară ascultătoare, veţi conveni ca aceasta să nu facă prea multă mizerie. Astfel, Taurina va face acele tăieturi în care ambele submulţimi sunt **conexe** (cu alte cuvinte, dacă ne-am uita pe rând la graful format din fiecare din cele două submulţimi complementare de noduri şi muchiile care le leagă, acesta este conex). Astfel, vor exista numai două bucăţi rezultate, iar mizeria va fi redusă la minimum.

Te-ai gândit mult la acest cadou şi ai convenit că îi vei da Taurinei un graf care să aibă exact $K$ tăieturi "frumoase". Mai mult, din motive financiare, nu îţi permiţi un graf cu mai mult de **64 de noduri**, deci bugetul trebuie ales cu atenţie.

Te-ai gândit mult la acest cadou şi ai convenit că îi vei da Taurinei un graf care să aibă exact $K$ tăieturi "frumoase". Mai mult, din motive financiare, nu îţi permiţi un graf cu mai mult de **80 de noduri**, deci bugetul trebuie ales cu atenţie.

Te uiţi pe calendar. Ziua ei e astăzi. Grăbeşte-te, nu vrei să îi oferi apă minerală, ca în ceilalţi ani!

h2. Date de ieşire

În fişierul de ieşire $cutit.out$ va conţine:

Fişierul de ieşire $cutit.out$ va conţine:

* pe prima linie două numere naturale $N$, $M$, reprezentând numărul de noduri, respectiv numărul de muchii al grafului-cadou
* pe următoarele $M$ linii, câte o muchie **distinctă** a grafului, dată printr-o pereche $(u, v)$ cu semnificaţia _"există o muchie neorientată între nodurile $u$, respectiv $v$"_
h2. Restricţii

* $1 ≤ K ≤ 10000$
* Graful afişat trebuie să aibă numărul de noduri cel mult egal cu $64$

* $1 ≤ K ≤ 10^4^$
* Graful afişat trebuie să aibă numărul de noduri cel puţin egal cu $1$ şi cel mult egal cu $80$

* **Graful afişat trebuie să fie conex**
h2. Exemplu
table(example). |_. cutit.in |_. cutit.out |
| 4

| 5 4

| 4 4

  1 2
  2 3

  3 1

  3 4

  4 5

|
h3. Explicaţie
Există exact $4$ tăieturi care respectă condiţia din enunţ:

* ${1}$, ${2, 3, 4, 5}$
* ${1, 2}$, ${3, 4, 5}$
* ${1, 2, 3}$, ${4, 5}$
* ${1, 2, 3, 4}$, ${5}$

* ${1}$, ${2, 3, 4}$
* ${2}$, ${1, 3, 4}$
* ${4}$, ${1, 2, 3}$
* ${1, 2}$, ${3, 4}$

== include(page="template/taskfooter" task_id="cutit") ==