Now Mr. MAZ is running short on sleeping pills, so he is searching them from planets to planets.
Finally he reaches the planet where he finds them.
There are many countries and in each country there may be one or more cities and a country can be a part of another country. Each city has 0 (zero) or more sleeping pills. Cities are connected by unidirectional paths.
A country is defined as a group of well connected cities such that if we start from any city of that country we can come back to that same city following the unidirectional paths.
Mr. MAZ is allowed to visit only one country. You being his favorite student, he asked you to help him select the country that has maximum number of pills.

Input:
First line of test file contains T, denoting number of test cases.
Next line of each test case contain two space separated integers N and M. N - number of cities and M - number of paths.
Next line contain N space separated integers denoting the number of pills in i^th city.
Next M lines each contains two space separated integers A and B denoting path from A to B.

Output:
For each test case output single integer containing maximum number of pills that he can collect by visiting only one country.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100
0 ≤ Number of pills in cities ≤ 1000
0 ≤ M ≤ N(N-1)
0* ≤ A,B < N

No Partial Marking for this question

Problem Setter: Prashant Arya

SAMPLE INPUT
3
5 5
2 3 5 11 12
0 1
1 2
2 0
2 3
3 4
5 5
2 3 5 1 2
0 1
1 2
2 0
2 3
3 4
5 6
2 3 4 1 3
0 1
1 2
2 0
1 3
3 4
4 2

SAMPLE OUTPUT
12
10
13

见题面

见题面