강한 연결 요소 (점진적)

$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$로, 그렇지 않으면 $0$으로 정의한다.
• $X = \sum_{0\leq i<j\leq N-1}\mathrm{same}(i,j)x_ix_j$을 정의한다.

제약 조건

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

$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$로 나눈 나머지를 출력한다.