题目描述

圣诞老人正在北极布置装饰。他计划用 $M$ 条双向导线连接 $N$ 个花环，花环编号为 $1\ldots N$。第 $i$ 条导线连接花环 $A_i$ 与 $B_i$。

这些导线可能形成环，但每条边最多属于一个简单环。也就是说，给出的图是一张仙人掌图。

花环 $i$ 上有 $C_i$ 盏灯，其中：

$$0\le C_i\le N-1$$

不同花环的 $C_i$ 不一定互不相同。

对于一条简单路径

$$P=[v_1,v_2,\ldots],$$

定义：

$$\operatorname{mex}(P)=\operatorname{mex}(\{C_{v_1},C_{v_2},\ldots\}),$$

也就是路径上所有花环灯数集合的最小未出现非负整数。

对于两个点 $s,t$，定义：

$$f(s,t)=\max \operatorname{mex}(P),$$

其中最大值在所有从 $s$ 到 $t$ 的简单路径 $P$ 中取得。

请计算所有无序点对 $(s,t)$ 的 $f(s,t)$ 之和。

例如在样例 2 中，从花环 $1$ 到花环 $2$ 有两条简单路径：

• $1\to2$，其 $\operatorname{mex}(\{0,1\})=2$；
• $1\to3\to4\to2$，其 $\operatorname{mex}(\{0,2,4,1\})=3$。

因此 $f(1,2)=3$。

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

每个测试用例：

• 第一行包含两个整数 $N,M$；
• 第二行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$；
• 接下来 $M$ 行，每行包含两个整数 $A_i,B_i$，表示一条边。

输出格式

对于第 $i$ 个测试用例，输出：

Case #i: ans

其中 ans 为所有无序点对 $(s,t)$ 的 $f(s,t)$ 之和。

数据范围

$$1\le T\le100$$ $$3\le N\le100$$ $$1\le A_i,B_i\le N, \quad A_i\ne B_i$$ $$0\le C_i<N$$

同一测试用例中，所有无序边 $(A_i,B_i)$ 互不相同。

保证给出的图是一张仙人掌图，也就是说图连通，并且任意两个简单环最多只有一个公共点。

样例说明

第一组样例中：

• $f(1,2)=3$：路径 $1\to3\to2$ 使得 $\operatorname{mex}(\{0,2,1\})=3$；
• $f(1,3)=3$：路径 $1\to2\to3$ 使得 $\operatorname{mex}(\{0,1,2\})=3$；
• $f(1,4)=3$：路径 $1\to3\to2\to4$ 使得 $\operatorname{mex}(\{0,1,2,0\})=3$；
• $f(2,3)=3$：路径 $2\to1\to3$ 使得 $\operatorname{mex}(\{1,0,2\})=3$；
• $f(2,4)=2$：唯一简单路径 $2\to4$，$\operatorname{mex}(\{1,0\})=2$；
• $f(3,4)=3$：路径 $3\to1\to2\to4$ 使得 $\operatorname{mex}(\{2,0,1,0\})=3$。

答案为：

$$3+3+3+3+2+3=17.$$

样例输入

4
4 4
0 1 2 0
1 2
2 3
3 1
4 2
6 7
0 1 2 4 3 1
1 2
1 3
2 4
3 4
4 5
5 6
6 4
3 2
1 0 2
1 2
2 3
6 6
0 1 2 1 0 0
1 2
2 3
3 4
2 4
3 5
6 4

样例输出

Case #1: 17
Case #2: 47
Case #3: 6
Case #4: 32