romania

Romania

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

Poveste şi cerinţă...

Fie $P$ un poligon convex regulat cu $N$ vârfuri numerotate în ordine trigonometrică. Ai trasat la un moment dat $K$ diagonale *orientate* ale acestui poligon, cu proprietatea că oricare două dintre ele nu se intersectează decât, eventual, în capete. În cele ce urmează îl vom numi pe $x$ "sursă" a diagonalei $x -> y$. Nu ai păstrat desenul întreg, dar ţi-ai notat sursa fiecărei diagonale pe o foaie. Acum te întrebi dacă poţi recupera diagonalele având doar aceste informaţii.

h2. Date de intrare

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

Fişierul de intrare $romania.in$ va conţine pe prima sa linie numerele $N şi K$ având semnificaţia din enunţ. A doua linie conţine $K$ numere, reprezentând lista de vârfuri care sunt surse ale diagonalelor.

h2. Date de ieşire

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

În fişierul de ieşire $romania.out$ se vor afla $K$ linii, fiecare conţinând o pereche $x y$ seminficând faptul că ai ales diagonala *orientată* dinspre vârful $x$ spre vârful $y$. Dacă nu există soluţie, fişierul va conţine doar valoarea *-1*.

h2. Restricţii

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

* $3 ≤ N ≤ 100.000$
* Pentru teste in valoare de *40* de puncte $N ≤ 1.500$
* $1 ≤ K ≤ N - 3$
* Vârfurile din fişierul de intrare sunt numere naturale din intervalul $[1, N]$.
* Reamintim că se numeşte diagonală a poligonului orice segment care uneşte două vârfuri neconsecutive ale acestuia.
* Se acceptă orice soluţie corectă.
* Dacă vă întrebaţi de ce această problemă se numeşte România: nu mai ştim nici noi.

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

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

| 5 2
1 4
|1 3
4 1

|

h3. Explicaţie
 
...
 

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