QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓
[+3]

# 905. 三元环枚举

Statistics

Source: Library Checker

Statement

You are given a simple undirected graph, consisting of N vertices and M edges. The i-th edge is {ui,vi}. Each vertex has an integer value, and the value of i th vertex is xi.

Three vertices a,b,c(a<b<c) connected by three edges {a,b},{a,c},{b,c} are called triangle. Find the sum of xaxbxc over all triangles, and print the sum modulo 998244353 .

N 頂点 M 辺の単純無向グラフが与えられます。 i 番目の辺は {ui,vi} です。 各頂点 i には整数 xi が割り当てられています。

3 頂点 a,b,c(a<b<c) であって辺 {a,b},{a,c},{b,c} が全て存在するものを triangle と呼びます。 全ての triangle についての xaxbxc の和を 998244353 で割った余りを求めてください。

Constraints

  • 1N105
  • 1M105
  • 0xi<998244353
  • 0ui<N
  • 0vi<N
  • uivi
  • {ui,vi}{uj,vj} (ij)

Input

  • N M
  • x0 x1 xN1
  • u0 v0
  • u1 v1
  • uM1 vM1

Ouput

  • A

Example

Input

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

Output

36

0,2,3 and 1,2,3 are triangles. Print 36, which is the result of 134+234mod .

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