In Ancient Rome, a plan to defeat the barbarians was developed, but for its implementation, each city must be informed about it.

The northern part of the Roman Empire consists of $n$ cities connected by $m$ one-way roads. Initially, the $i$-th city has $a_i$ messengers, and each messenger can freely move between cities following the existing roads. A messenger can carry a copy of the plan with him and inform the cities he visits, and can make unlimited copies for other messengers in the city he is currently in.

At the start, you will produce some number of plans and deliver them to messengers of your choice. Your goal is to make sure that every city is visited by a messenger with a plan. Find the smallest number of the plans you need to produce originally, so that the messengers will deliver them to every city, or determine that it is impossible to do so at all.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line contains two integers $n$ and $m$ ($2 \le n \le 200$, $1 \le m \le 800$) — the number of cities and roads.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ ($0 \le a_{i} \le n$) — the initial number of messengers in each city.

Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n, u \ne v$), indicating that there is a one-way road from city $u$ to city $v$. The roads may repeat.

It is guaranteed that the sum of $n$ over all test cases does not exceed $200$. It is guaranteed that the sum of $m$ over all test cases does not exceed $800$.

Output

Output a single line containing a single integer — the smallest number of messengers you need to give a copy of the plan in the beginning, or $-1$ if it is not possible to inform all cities.