#6683. 「XXOI 2019」必须旗帜鲜明地反对毒瘤

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KingSann

题目描述

给定两张都是 n 个点, m 条边的图 G_1,G_2 ,点有点权,设 f_{t}(u,v) 表示第 t 张图,从 u v 的所有简单路径中,权值最小的简单路径

一个简单路径的权值定义为经过的点的权值最小值

求:

\sum_{1 \le i < j \le n} f_1(i,j) \times f_2(i,j)

输入格式

第一行两个整数 n,m

之后一行 n 个整数,表示第一张图的点权 v_{1,1},v_{1,2},v_{1,3},\cdots,v_{1,n}

之后一共 m 行,每行两个整数 u,v ,表示第一张图的 u,v 有一条无向边

之后一行 n 个整数,表示第二张图的点权 v_{2,1},v_{2,2},v_{2,3},\cdots,v_{2,n}

之后一共 m 行,每行两个整数 u,v ,表示第二张图的 u,v 有一条无向边

输出格式

一行一个整数表示答案模 998244353 意义下的值

样例

样例输入

5 4
6 6 6 8 2 
2 1
3 2
4 3
5 2
1 4 4 3 9 
2 1
3 2
4 1
5 1

样例输出

62

数据范围与提示

保证两个图都是连通图,且 1 \le n \le 10^5, n-1 \le m \le 10^6,1 \le v \le 10^6


感谢 @liuzhangfeiabc 提供的测试点 6 \sim 10