casute

Casute

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

Poveste si cerinta...

Nargy si Fumeanu au plecat la munte. Ei au o harta a muntelui, in care sunt identificate $N$ casute montane (numerotate cu numere distincte intre {$1$} si {$N$}), situate la diferite inaltimi (casuta $i$ se afla la inaltimea {$H{~i~}$}). Aceste casute sunt legate prin $M$ poteci. O poteca leaga doua casute distincte si poate fi parcursa doar intr-un singur sens: de la casuta situata la o inaltime mai mica catre casuta situata la o inaltime mai mare.
La un moment dat, cei doi s-au despartit si fiecare a ajuns in dreptul unei casute, dar din fericire fiecare avea la el o copie a hartii. Cei doi si-au telefonat si au stabilit un loc de intalnire, astfel: se vor intalni la casuta situata la inaltimea minima dintre acele casute la care pot ajunge amandoi (tineti minte ca nu pot decat urca).
Pentru a evita astfel de situatii in viitor, cei doi si-au propus sa determine locul in care s-ar fi intalnit indiferent de casutele in care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hartie, pentru fiecare pereche $i$ $j$ ({$1 &le; i < j &le; N$}), perechile fiind considerate in ordine lexicografica. In cazul in care pentru o anumita pereche nu exista o astfel de casuta de intalnire, se va scrie pe foaie numarul {$0$}.

h2. Date de intrare

...

Fisierul de intrare $casute.in$ contine pe prima linie numerele naturale $N$ si $M$ separate prin spatii. Urmatoarea linie va contine $N$ numere naturale separate prin spatii reprezentand inaltimile la care se afla casutele, in ordine de la $1$ la {$N$}. Urmatoarele $M$ linii vor contine cate doua numere naturale $i$ $j$ separate prin spatii, reprezentand o poteca de la casuta $i$ la casuta $j$ (se garanteaza ca {$H{~i~}<H{~j~}$}).

h2. Date de iesire

...

Cele $N*(N-1)/2$ valori pe care cei doi le vor scrie pe foaie pot fi considerate ca reprezinta cifrele unui numar scris in baza {$N+1$}. in fisierul de iesire $casute.out$ se va scrie pe prima linie restul impartirii acelui numar convertit in baza $10$ la numarul {$666013$}.

h2. Restrictii

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

* {$1 ≤ N ≤ 3.000$}
* {$1 ≤ M ≤ 30.000$}
* inaltimile celor $N$ casute sunt numere intregi distincte din intervalul [{$1,10^9^$}]
* Se considera ca o pereche de numere ({$a b$}) este mai mica din punct de vedere lexicografic decat o alta pereche de numere ({$c d$}), daca $a<c$ sau $a=c$ si $b<d$

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

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

| 5 7
1 2 3 4 5
1 3
2 3
1 4
2 4
2 5
4 5
3 5
| 24052

|
h3. Explicatie

...

{$(1 2) -> 3$}
{$(1 3) -> 3$}
{$(1 4) -> 4$}
{$(1 5) -> 5$}
{$(2 3) -> 3$}
{$(2 4) -> 4$}
{$(2 5) -> 5$}
{$(3 4) -> 5$}
{$(3 5) -> 5$}
{$(4 5) -> 5$}
{$3345345555{~(6)~} = 36654767{~(10)~} = 24052 (mod 666013)$}

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

1965