Fişierul intrare/ieşire:cutit.in, cutit.outSursăFMI No Stress 2017
AutorLucian BicsiAdăugată defmins7Fmi No Stress 7 fmins7
Timp execuţie pe test1 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cut It

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!

Date de intrare

Fişierul de intrare cutit.in va conţine un singur număr natural, K.

Date de ieşire

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"

Restricţii

  • 1 ≤ K ≤ 104
  • 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

Exemplu

cutit.incutit.out
4
4 4
1 2
2 3
3 1
3 4

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}
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?