# Enumerate Triangles

AC一覧

## Problem Statement問題文

You are given a simple undirected graph, consisting of $N$ vertices and $M$ edges. The $i$-th edge is $\lbrace u_i, v_i \rbrace$. Each vertex has an integer value, and the value of $i$ th vertex is $x_i$.

Three vertices $a, b, c (a \lt b \lt c)$ connected by three edges $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ are called triangle. Find the sum of $x_a x_b x_c$ over all triangles, and print the sum modulo $998{,}244{,}353$ .

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。 $i$ 番目の辺は $\lbrace u_i, v_i \rbrace$ です。 各頂点 $i$ には整数 $x_i$ が割り当てられています。

3 頂点 $a, b, c (a \lt b \lt c)$ であって辺 $\lbrace a, b \rbrace, \lbrace a, c \rbrace, \lbrace b, c \rbrace$ が全て存在するものを triangle と呼びます。 全ての triangle についての $x_a x_b x_c$ の和を $998{,}244{,}353$ で割った余りを求めてください。

## Constraints制約

• $1 \le N \le 100{,}000$
• $1 \le M \le 100{,}000$
• $0 \le x_i \lt 998{,}244{,}353$
• $0 \le u_i \lt N$
• $0 \le v_i \lt N$
• $u_i \neq v_i$
• $\lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace \ (i \neq j)$

## Input入力

$N$ $M$
$x_0$ $x_1$ $\ldots$ $x_{N-1}$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{M-1}$ $v_{M-1}$


## Output出力

$A$


## Sampleサンプル

### # 1

4 5
1 2 3 4
0 3
2 0
2 1
2 3
1 3

36


$0, 2, 3$ and $1, 2, 3$ are triangles. Print $36$, which is the result of $1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4 \bmod 998{,}244{,}353$ .

$0, 2, 3$ 及び $1, 2, 3$ が triangle です。 $1 \cdot 3 \cdot 4 + 2 \cdot 3 \cdot 4$ を $998{,}244{,}353$ で割った余りである $36$ を出力します。

Timelimit: 5 secs

Before submitting, please confirm terms and conditions