Fişierul intrare/ieşire:perechi2.in, perechi2.outSursăRomanian Open Contest, TIMUS 2001
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.075 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inperechi2.out
7 12
1 2
1 3
2 3
3 4
4 5
4 6
4 7
5 6
5 7
6 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content