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 Hi). 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≤i<j≤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ă Hi<Hj).

Date de ieşire

Cele N*(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

1 ≤ N ≤ 3 000
1 ≤ M ≤ 30 000
Înălţimile celor N căsuţe sunt numere întregi distincte din intervalul [1,10⁹]
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

Exemple

casute.in	casute.out	Explicaţii
5 7 1 2 3 4 5 1 3 2 3 1 4 2 4 2 5 4 5 3 5	24052	(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)

autor: Mircea Paşoi

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com