Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | perechi2.in, perechi2.out | Sursă | Romanian Open Contest, TIMUS 2001 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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).
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.
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.
Restrictii
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ N*(N-1)/2
- Intre 2 calculatoare poate exista cel mult o conexiune.
Exemplu
| 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 |
