## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ 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:

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

Find the first moment of time when all ${a}_{i}$ become $0$. Since the answer can be very large, output it

Solution Click Below:-  👉

👇👇👇👇👇

modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Input

The first line contains a single integer $t$ ($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$ ($1\le n,m\le 1000$) — the number of vertices and edges in the graph.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($0\le {a}_{i}\le {10}^{9}$) — the integer on vertices.

Each line of the following $m$ lines contains two integers $x,y$ ($1\le x,y\le 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\phantom{\rule{thinmathspace}{0ex}}000$.

Output

For each test case, print an integer in a separate line — the first moment of time when all ${a}_{i}$ become $0$, modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.