Perechi2

perechi2

== include(page="template/taskheader" task_id="perechi2") ==

O companie romaneasca producatoare de software a cumparat $N$ calculatoare, care vor fi conectate in retea. O conexiune poate fi stabilita intre oricare $2$ calculatoare distincte si este bidirectionala (daca cele $2$ calculatoare sunt etichetate cu $i$ si $j$, atunci se pot transmite date atat de la $i$ la $j$, cat si de la $j$ la $i$). Determinati o modalitate de a interconecta cele $N$ calculatoare astfel inca oricare $2$ calculatoare sa poata transmite date de la unul la altul (direct sau indirect, folosind alte calculatoare intermediare). Exista o singura cerinta suplimentara: reteaua formata trebuie sa contina exact $K$ perechi critice. O pereche $(i,j)$ este critica daca exista o conexiune pe care daca am inlatura-o, atunci nu s-ar mai putea transmite date de la $i$ la $j$ (si nici invers).

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $perechi2.in$ contine $2$ numere intregi, separate printr-un spatiu: $N$, numarul de calculatoare, si $K$, numarul de perechi critice.

...

h2. Date de iesire

In fisierul de iesire $perechi2.out$ veti afisa conexiunile ce formeaza reteaua, cate o conexiune pe linie. Pentru fiecare conexiune afisati $2$ numere intregi, separate printr-un spatiu: $i$ si $j$, reprezentand cele $2$ calculatoare conectate direct cu ajutorul conexiunii respective. Daca nu se poate forma o retea avand $K$ perechi critice, afisati in fisierul de iesire doar numarul $-1$.

...

h2. Restrictii

* $1 ≤ N ≤ 100$
* $0 ≤ K ≤ N*(N-1)/2$
* Intre $2$ calculatoare poate exista cel mult o conexiune.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. perechi2.in |_. perechi2.out |

|7 12
|1 2
1 3
2 3
3 4
4 5
4 6
4 7
5 6
5 7
6 7

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicatie
 
...
 

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

2301