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

Poveste şi cerinţă...

bq. Pe-un picior de plai,
Pe-o gură de rai,
Iată vin în cale,
Se cobor la vale,
Douăzeci de turme de miei,
Cu douăzeci de ciobănei.
 
În această extindere a baladei Mioriţa ciobănaşii noştri se confruntă cu 'Fenrir':http://en.wikipedia.org/wiki/Fenrir, un personaj al mitologiei nordice, care după o uşoară confuzie de natură geografică a ajuns şi el pe acelaşi picior de plai. Mai mult, acesta urmează să atace turmele la lăsarea serii. Plictisiţi de atitudinea ciobănaşului moldovean, care începuse din nou să-şi plănuiască funeraliile, ceilalţi au hotărât să adopte o poziţie mai pragmatică şi să înfrunte problema. Ei au concluzionat că problema se poate formula astfel:
 
Cei douăzeci de ciobănaşi au douăzeci de stâne, fiecare stână adăpostind o turmă de miei. Aceştia pot construi cărări directe, bidirecţionale, între oricare două stâne. Ei ştiu că Fenrir va lovi o singură dată, la lăsarea serii, trecând prin fiecare stână maxim o dată (fiind un animal mitologic relativ ocupat) şi nimicind turmele din stânele respective. Cunoscând acest lucru ciobănaşii vor să construiască o reţea de cărări care să le asigure o bună comunicare pe parcursul atacului, dar în acelaşi timp să nu uşureze prea mult deplasarea lui Fenrir. Mai exact, reţeaua de cărări trebuie să respecte următoarele proprietăţi
 
1. Trebuie să nu existe un drum format din cărări care să viziteze toate cele $20$ de stâne exact o dată. Altfel, Fenrir îl va folosi cu siguranţă şi va consuma toate cele $20$ de turme, ceea ce ar fi dezastruos pentru ciobănaşi. Protejând măcar o turmă pe parcursul atacului, aceştia ar putea repopula şi celelalte stâne mai apoi.
 
2. Trebuie ca oricare două stâne să fie legate, direct sau indirect, prin cărări. Mai mult, dacă ar fi să numărăm stânele vecine pentru fiecare stână, minimul acestor valori ar trebui să fie cât mai mare.
 
Ciobănaşii nu au timp de generalizări, aşa că trebuie să rezolvaţi această problemă doar pentru acest caz cu $20$ de stâne. În schimb, punctajul vostru va depinde de numărul minim de vecini ai unei stâne în soluţia pe care o oferiţi. Mai exact, dacă notăm acest număr cu $cMin$, punctajul vostru va fi
 
$Punctaj = (cMin + 1)^2^$

h2. Date de intrare

Fişierul de intrare $fenrir.in$ ...

Fişierul de intrare $fenrir.in$ nu conţine nimic relevant pentru programul vostru, din motive evidente. Vom pune totuşi acolo versiunea integrală a baladei Mioriţa, în cazul în care doriţi să o citiţi.

h2. Date de ieşire

În fişierul de ieşire $fenrir.out$ ...

Prima linie din fişierul de ieşire $fenrir.out$ va conţine un număr $M$, reprezentând numărul total de cărări din soluţia voastră. Următoarele $M$ linii vor conţine câte o pereche de numere *distincte* $X Y$, seminficând faptul că stânele cu numărul $X$ şi $Y$ sunt legate printr-o cărare bidirecţională. Aceste numere trebuie să se afle în intervalul $[1, 20]$. Toate perechile afişate trebuie să fie *distincte*.

h2. Restricţii

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

* $Numărul de stâne = 20$

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

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

| Pe-un picior de plai,
Pe-o gură de rai,
Iată vin în cale,
Se cobor la vale,
...
| 5
1 10
2 10
5 14
2 20
1 20

|
h3. Explicaţie

...

Această soluţie ar obţine 0 puncte, deoarece nu asigură un drum între oricare două stâne.

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

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