[Solution] Count Seconds Codeforces Solution

E. Count Seconds

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Cirno has a DAG (Directed Acyclic Graph) with n$n$ nodes and m$m$ edges. The graph has exactly one node that has no out edges. The i$i$-th node has an integer ai$a_i$ on it.

Every second the following happens:

• Let S$S$ be the set of nodes x$x$ that have ax>0$a_x>0$.
• For all x∈S$x\in S$, 1$1$ is subtracted from ax$a_x$, and then for each node y$y$, such that there is an edge from x$x$ to y$y$, 1$1$ is added to ay$a_y$.

Find the first moment of time when all ai$a_i$ become 0$0$. Since the answer can be very large, output it

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 modulo 998244353$998244353$.

Input

The first line contains a single integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers n,m$n,m$ (1≤n,m≤1000$1\le n,m\le 1000$) — the number of vertices and edges in the graph.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai≤109$0\le a_i\le {10}^9$) — the integer on vertices.

Each line of the following m$m$ lines contains two integers x,y$x,y$ (1≤x,y≤n$1\le x,y\le n$), represent a directed edge from x$x$ to y$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$n$ and sum of m$m$ over all test cases are less than or equal to 10000$10000$.

Output

For each test case, print an integer in a separate line — the first moment of time when all ai$a_i$ become 0$0$, modulo 998244353$998244353$.