Abstract

Time limit: 2000 ms. Memory limit: 2048 MB.

정점이 $n$개, 간선이 $m$개인 DAG(방향 비순환 그래프)가 주어진다. 나가는 간선이 없는 정점 $x$가 정확히 하나 있다. $i$번 정점에는 정수 $a_i$가 적혀 있다.

매초 다음 과정이 일어난다.

• 각 정점 $i$에 대해 $b_i = a_i$로 둔다.
• 각 정점 $i$에 대해 $a_i = 0$으로 둔다.
• 각 정점 $i$와 $i$에서 $j$로 가는 간선이 있는 각 정점 $j$에 대해, $b_i$를 $a_j$에 더한다.
• $\lfloor b_x / 2 \rfloor$를 $a_x$에 더한다.

모든 $a_i$가 처음으로 0이 되는 시각을 구한다. 답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구한다.

첫째 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($1 \le n \le 10^4$; $1 \le m \le 10^5$).

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)이 주어진다.

이어지는 $m$개의 줄에는 각각 $u$에서 $v$로 가는 간선을 나타내는 두 정수 $u$, $v$ ($1 \le u, v \le n$)가 주어진다.

그래프는 다중 간선이 없는 DAG이며, 나가는 간선이 없는 정점은 정확히 하나라고 보장된다.

모든 $a_i$가 처음으로 0이 되는 시각을 $998\,244\,353$으로 나눈 나머지로 한 줄에 출력한다.

이 문제는 Codeforces 1704E와 공교롭게도 매우 비슷하다.