Abstract

You have a DAG (Directed Acyclic Graph) with $n$ nodes and $m$ edges. The graph has exactly one node $x$ that has no outgoing edges. The $i$-th node has an integer value $a_i$ in it.

Every second, the following happens:

• For each node $i$, let $b_i=a_i$.
• For each node $i$, let $a_i=0$.
• For each node $i$, and each node $j$ such that there is an edge from $i$ to $j$, the value $b_i$ is added to $a_j$.
• The value $\left\lfloor \frac{b_x}{2} \right\rfloor$ is added to $a_x$.

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 two integers $n$ and $m$ ($1\leq n\leq 10^4$; $1 \leq m \leq 10^5$): the number of vertices and edges in the graph.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$): the values in the vertices.

Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$) which represent a directed edge from $u$ to $v$.

It is guaranteed that the graph is a DAG with no multi-edges, and there is exactly one node that has no outgoing edges.

Print a line with a single integer: the first moment of time when all $a_i$ become $0$, modulo $998\,244\,353$.

Hi, so to me seems like a notorious coincidence. (Codeforces 1704E)