D. 为了皇帝！
每个测试点时间限制：$2$ 秒
每个测试点内存限制：$256$ 兆字节

在古罗马，人们制定了一个击败蛮族的计划，但为了实施该计划，必须让每个城市都知晓它。

罗马帝国的北部由 $n$ 个城市组成，城市之间由 $m$ 条单向道路连接。初始时，第 $i$ 个城市有 $a_i$ 名信使，每名信使可以按照现有道路自由地在城市间移动。信使可以随身携带一份计划副本，并告知他所访问的城市，同时他可以在当前所在的城市为其他信使制作无限份计划副本。

开始时，你会制作一定数量的计划，并将它们交给你选择的信使。你的目标是确保每个城市都被至少一名携带计划的信使访问。请找出最初需要制作的最少计划数量，使得信使们能将计划传递到所有城市；如果不可能做到，则输出 $-1$。

输入
每个测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 100$），表示测试用例的数量。
每个测试用例的描述如下：
第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 200$，$1 \le m \le 800$）——城市数量和道路数量。
第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）——每个城市的初始信使数量。
接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示有一条从城市 $u$ 到城市 $v$ 的单向道路。道路可能重复。
保证所有测试用例的 $n$ 之和不超过 $200$。保证所有测试用例的 $m$ 之和不超过 $800$。

输出
输出一行一个整数，表示最初需要给予计划副本的最少信使数量；如果不可能通知到所有城市，则输出 $-1$。

样例

输入

2
7 6
2 1 0 1 2 3 4
1 2
1 3
2 4
2 5
3 6
3 7
4 4
1 1 1 1
1 2
1 3
2 4
3 4

输出

2
2