h2. Date de intrare

Fişierul de intrare $easygraph.in$ conţine pe prima linie numărul de teste, $T$. În continuare, pentru fiecare test, se vor găsi pe prima linie două numere naturale $N$ şi $M$, având semnificaţia din enunţ. Pe cea de-a doua linie, se vor găsi $N$ numere întregi, elementele vectorului $v[i]$. Pe următoarele $M$ linii se vor găsi câte două numere $x$ şi $y$, cu semnificaţia că există un arc de la nodul $x$ la nodul $y$.

Fişierul de intrare $easygraph.in$ conţine pe prima linie numărul de teste, $T$. În continuare, pentru fiecare test, se vor găsi pe prima linie două numere naturale $N$ şi $M$, având semnificaţia din enunţ. Pe cea de-a doua linie, se vor găsi $N$ numere naturale, elementele vectorului $v[i]$. Pe următoarele $M$ linii se vor găsi câte două numere $x$ şi $y$, cu semnificaţia că există un arc de la nodul $x$ la nodul $y$.

h2. Date de ieşire

h2. Restricţii
* $T = 20$

* $1 ≤ N ≤ 15.000$
* $1 ≤ M ≤ 30.000$

* $1 ≤ N ≤ 2.000$
* $1 ≤ M ≤ 4.000$

* $-10^6^ ≤ v[i] ≤ 10^6^$
* $Pot exista mai multe arce între aceleaşi noduri X şi Y.$

* $Lanţul găsit de sumă maximă trebuie să conţină cel puţin 1 nod.$

h2. Exemplu

9416