增量强连通分量

【题目描述】

有一个 $N$ 个顶点、$0$ 条边的有向图 $G$，以及一个整数序列 $x_0, \ldots, x_{N-1}$。

向 $G$ 中加入 $M$ 条有向边，第 $i$ 条边从 $a_i$ 指向 $b_i$。

每加入一条边之后，输出下式定义的 $X$ 对 $998244353$ 取模的结果：

• 对 $0\leq i,j \leq N-1$，若顶点 $i$ 与顶点 $j$ 在 $G$ 中属于同一个强连通分量，则定义 $\mathrm{same}(i,j)=1$，否则 $\mathrm{same}(i,j)=0$。
• 定义 $X = \sum_{0\leq i<j\leq N-1}\mathrm{same}(i,j)x_ix_j$。

【输入】

$N$ $M$
$x_0$ $\ldots$ $x_{N-1}$
$a_0$ $b_0$
$a_1$ $b_1$
$\vdots$
$a_{M - 1}$ $b_{M - 1}$

【输出】

每加入一条边后，输出一行，即此时 $X$ 对 $998244353$ 取模的结果。

【输入样例】

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

【输出样例】

0
0
3
3
3
6

【输入样例2】

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

【输出样例2】

0
0
2984
2984
2984
10940

【输入样例3】

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

【输出样例3】

0
0
0
0
0
0
408

【数据范围】

• $1 \leq N \leq 500000$
• $1 \leq M \leq 500000$
• $0 \leq x_i < 998244353$
• $0 \leq a_i, b_i < N$

【来源】

Library Checker（yosupo06） incremental_scc