B'Cirno has a DAG (Directed Acyclic Graph) with n nodes and m edges. The graph has exactly one node that has no out edges. The i -th node has an integer a_i on it. Every second the following happens: Find the first moment of time when all a_i become 0 . Since the answer can be very large, output it modulo 998 ,244 ,353 . The first line contains a single integer t ( 1 <= q t <= q 1000 ) -- the number of test cases. Description of test cases follows. The first line of each test case contains two integers n, m ( 1 <= q n, m <= q 1000 ) -- the number of vertices and edges in the graph. The second line of each test case contains n integers a_1, a_2, ldots, a_n ( 0 <= q a_i <= q 10^9 ) -- the integer on vertices. Each line of the following m lines contains two integers x, y ( 1 <= q x, y <= q n ), represent a directed edge from x to y . It is guaranteed that the graph is a DAG with no multi-edges, and there is exactly one node that has no out edges. It is guaranteed that both sum of n and sum of m over all test cases are less than or equal to 10 ,000 . For each test case, print an integer in a separate line -- the first moment of time when all a_i become 0 , modulo 998 ,244 ,353 . In the first test case: So the answer is 3 . In the third test case: The first moment of time when all a_i become 0 is 6 cdot 998244353 + 4 . '...