强连通分量（增量式）（Strongly Connected Components (Incremental)）

问题描述

初始时，给定一个含 $N$ 个顶点、0 条边的有向图 $G$，以及一个整数序列 $x_0, x_1, \dots, x_{N-1}$。
随后依次添加 $M$ 条有向边：第 $i$ 条边从 $a_i$ 指向 $b_i$。

每次添加一条边后，定义：

• $\text{same}(i,j) = \begin{cases} 1 & \text{若 } i,j \text{ 属于同一强连通分量} \\ 0 & \text{否则} \end{cases}$，其中 $0 \le i,j \le N-1$；
• $X = \sum_{0 \le i < j \le N-1} \text{same}(i,j) \cdot x_i x_j$。

请输出每次添加边后的 $X \bmod 998244353$。

约束条件

• $1 \leq N, M \leq 5 \times 10^5$
• $0 \leq x_i < 998244353$
• $0 \leq a_i, b_i < N$

输入格式

$N\ M$
$x_0\ x_1\ \cdots\ x_{N-1}$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{M-1}\ b_{M-1}$

4 6
1 1 1 1
0 1
1 2
2 0
2 3
1 3
3 0

0
0
3
3
3
6

4 6
12 34 56 78
0 1
1 2
2 0
2 3
1 3
3 0

0
0
2984
2984
2984
10940

2 7
12 34
0 0
1 1
0 0
0 1
1 1
0 1
1 0

0
0
0
0
0
0
408