在古罗马,制定了一项击败野蛮人的计划,但为了实施该计划,必须向每个城市通报该计划。
罗马帝国北部由 $$$n$$$ 个城市组成,由 $$$m$$$ 单向道路连接。最初,第 $$$i$$$ 个城市有 $$$a_i$$$ 信使,每个信使可以沿着现有道路在城市之间自由移动。信使可以随身携带一份计划并通知他所访问的城市,并可以为当前所在城市的其他信使无限复制。
一开始,您将制定一些计划并将其发送给您选择的信使。你的目标是确保每个城市都有一个有计划的使者访问。找到你最初需要制作的最少数量的计划,以便使者将它们交付到每个城市,或者确定根本不可能这样做。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 200$$$, $$$1 \le m \le 800$$$) — 城市和道路的数量。
第二行包含 $$$n$$$ 非负整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_{i} \le n$$$) — 每个城市的初始信使数量。
下面的$$$m$$$行中每一行都包含两个整数$$$u$$$和$$$v$$$ ($$$1 \le u,v \le n, u \ne v$$$),表示从城市$$$u$$$到城市$$$v$$$有一条单向道路。道路可能会重复。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$200$$$。 保证所有测试用例的 $$$m$$$ 总和不超过 $$$800$$$。
输出
输出包含单个整数的单行 — 您在开始时提供计划副本所需的最少信使数量,如果无法通知所有城市,则为 $$$-1$$$。
示例
输入 #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
输出 #1
2 2