casute

Enunț

Nargy şi Fumeanu au plecat la munte. Ei au o hartă a muntelui, în care sunt identificate $N$ căsuţe montane (numerotate cu numere distincte între $1$ şi $N$), situate la diferite înălţimi (căsuţa $i$ se află la înălţimea $H_i$). Aceste căsuţe sunt legate prin $M$ poteci. O potecă leagă două căsuţe distincte şi poate fi parcursă doar într-un singur sens: de la căsuţa situată la o înălţime mai mică către căsuţa situată la o înălţime mai mare.

La un moment dat, cei doi s-au despărţit şi fiecare a ajuns în dreptul unei căsuţe, dar din fericire fiecare avea la el o copie a hărţii. Cei doi şi-au telefonat şi au stabilit un loc de întâlnire, astfel: se vor întâlni la căsuţa situată la înălţimea minimă dintre acele căsuţe la care pot ajunge amândoi (ţineţi minte că nu pot decât urca).

Pentru a evita astfel de situaţii în viitor, cei doi şi-au propus să determine locul în care s-ar fi întâlnit indiferent de căsuţele în care s-ar fi aflat cei doi. Ei vor trece aceste rezultate pe o foaie de hârtie, pentru fiecare pereche $i \ j \ (1 \leq i < j \leq N)$, perechile fiind considerate în ordine lexicografică. În cazul în care pentru o anumită pereche nu există o astfel de căsuţă de întâlnire, se va scrie pe foaie numărul $0$.

Cerință

Scrieţi un program care determine pentru cei doi toate aceste informaţii, având la dispoziţie harta muntelui.

Date de intrare

Fişierul de intrare casute.in conţine pe prima linie numerele naturale $N$ şi $M$ separate prin spaţii. Următoarea linie va conţine $N$ numere naturale separate prin spaţii reprezentând înălţimile la care se află căsuţele, în ordine de la $1$ la $N$. Următoarele $M$ linii vor conţine câte două numere naturale $i \ j$ separate prin spaţii, reprezentând o potecă de la căsuţa $i$ la căsuţa $j$ (se garantează că $H_ i < H_j$).

Date de ieșire

Cele $\frac{N \times (N - 1)}{2}$ valori pe care cei doi le vor scrie pe foaie pot fi considerate că reprezintă cifrele unui număr scris în baza $N + 1$. În fişierul de ieşire casute.out se va scrie pe prima linie restul împărţirii acelui număr convertit în baza $10$ la numărul $666013$.

Restricții și precizări

• $1 \leq N \leq 3 \ 000$;
• $1 \leq M \leq 30 \ 000$;
• Înălţimile celor $N$ căsuţe sunt numere întregi distincte din intervalul $[1, 10^9]$
• Se consideră că o pereche de numere $(a \ b)$ este mai mică din punct de vedere lexicografic decât o altă pereche de
  numere $(c \ d)$, dacă $a < c$ sau $a = c$ şi $b < d$

Exemplu

casute.in

5 7
1 2 3 4 5
1 3
2 3
1 4
2 4
2 5
4 5
3 5

casute.out

24052

Explicație

$(1 \ 2) \rightarrow 3$
$(1 \ 3) \rightarrow 3$
$(1 \ 4) \rightarrow 4$
$(1 \ 5) \rightarrow 5$
$(2 \ 3) \rightarrow 3$
$(2 \ 4) \rightarrow 4$
$(2 \ 5) \rightarrow 5$
$(3 \ 4) \rightarrow 5$
$(3 \ 5) \rightarrow 5$
$(4 \ 5) \rightarrow 5$
$3345345555_{(6)} = 36654767_{(10)} = 24052 \ (mod \ 666013)$