题目描述
P 国有 N 座城市和 M 条无向道路,其中 1 号城市是首都,且任意两座城市都能通过道路互相到达。
现在 P 国要在首都召开 ION。为了建设比赛场地,每个城市都要向首都提供原材料,其中第 i 座城市可以提供类型为 ci 的原材料。每座城市都会有货车从该城市出发,沿简单路径前往首都。如果从城市 A 出发的货车必须经过城市 B ,那么我们称城市 B 在城市 A 到首都的必经之路上。如果对于城市 A,B,C,从 B 到 A 的任意简单路径与 C 到 A 的任意简单路径没有公共边,那么我们称城市 B 和城市 C 关于城市 A 互不影响。
记 f(A,k) 为满足下列所有条件的 k 元集合 {B1,B2,⋯Bk} 的个数:
-
对于任意 1≤i≤k 满足 A=Bi,城市 A 在城市 Bi 到首都的必经之路上且城市 Bi 供应的材料与城市 A 不同。
-
对于任意 1≤i<j≤k 满足 Bi 与 Bj 关于 A 互不影响,且 Bi 和 Bj 供应的原材料相同。
定义举办 ION 的吸引力为∑i=1N∑k=1Kf(i,k),其中 K 是给定的常数。
现在,你作为 P 国的首脑,你想要知道这次 ION 的吸引力。
由于答案可能很大,所以请将答案对 998244353 取模。
输入格式
第一行三个整数 N,M,K。
第二行 N 个整数,第 i 个数第 i 座城市供应的原材料类型 ci。
接下来 M 行,每行两个整数 u,v ,表示 P 国的一条道路。保证没有重边,没有自环。(1≤u,v≤N,u=v)
输出格式
一行一个整数表示答案。
提示
【样例解释】
样例中 P 国的地图如下:

下表中,第 i 行第 j 列表示 f(i,j)。
4 |
0 |
4 |
0 |
0 |
2 |
1 |
1 |
0 |
所以吸引力为 4+4+2+1+1=12。
【数据范围】
本题采用捆绑测试。
- Subtask1(10pts):N,K≤8;
- Subtask2(10pts):K=1;
- Subtask3(15pts):K=2;
- Subtask4(15pts):保证图的形态为一棵树;
- Subtask5(15pts):N≤2000;
- Subtask6(15pts):N≤4×104;
- Subtask7(20pts):无特殊限制。
对于 100% 的数据满足,1≤N≤5×105, 1≤M≤min(106,2N×(N−1)),1≤K≤20,1≤ci≤109。
温馨提示:输入量较大,请使用较快的读入方式。