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

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

题目描述

给定两张都是 nn 个点,mm 条边的图 G1,G2G_1,G_2,点有点权,设 ft(u,v)f_{t}(u,v) 表示第 tt 张图,从 uuvv 的所有简单路径中,权值最小的简单路径

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

求:

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

输入格式

第一行两个整数 n,mn,m

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

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

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

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

输出格式

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

样例

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 提供的测试点 6106 \sim 10