== include(page="template/taskheader" task_id="cutit") ==
Poveste şi cerinţă...
h3. _V-am tăiat şi pofta de pizza cu problema asta_
Probabil cea mai tăioasă problemă din tot concursul (sperăm că nu şi cea mai tăioasă _dumă_). Urmează ziua surioarei tale mai mici, Taurina. Taurina este oarecum pasionată de informatică (bineînţeles, nu ca tine, dar speri că într-o zi îţi va călca pe urme), de aceea te-ai gândit la un cadou cu totul şi cu totul special pentru o fetiţă specială: **un graf neorientat**!
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 **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 intrare
Fişierul de intrare $cutit.in$ ...
Fişierul de intrare $cutit.in$ va conţine un singur număr natural, $K$.
h2. Date de ieşire
În fişierul de ieşire $cutit.out$ ...
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 ≤ 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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
| 4 4
1 2
2 3
3 1
3 4
|
h3. Explicaţie
...
Există exact $4$ tăieturi care respectă condiţia din enunţ:
* ${1}$, ${2, 3, 4}$
* ${2}$, ${1, 3, 4}$
* ${4}$, ${1, 2, 3}$
* ${1, 2}$, ${3, 4}$
== include(page="template/taskfooter" task_id="cutit") ==
