给定一个包含 $N$ 个节点和 $M$ 条边的连通无向图 $G$。每条边的权重均为 1。 部分节点被标记，其余节点未被标记。给定一个二进制字符串 $S$，当且仅当节点 $i$ 被标记时，$S_i = 1$。

令 $X$ 为所有被标记节点的集合。保证 $X$ 非空。在子集 $X$ 上构造一个完全加权图 $H$。节点 $u$ 和 $v$ 之间边的权重为 $\text{dist}(u, v)^\dagger$，其中距离是在原图 $G$ 中测量的。

求图 $H$ 中最小生成树的权重总和。

$^\dagger \text{dist}(u, v)$ 是 $u$ 和 $v$ 之间的最短路径长度。路径长度由路径中的边数衡量。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含多行输入：
  • 第一行包含 $N$ 和 $M$，分别表示节点数和边数。
  • 第二行包含一个长度为 $N$ 的二进制字符串 $S$。
  • 接下来的 $M$ 行，每行包含 2 个整数 $u$ 和 $v$，表示图 $G$ 中的一条边 $(u, v)$。

输出格式

对于每个测试用例，输出一行，表示构造出的图 $H$ 的最小生成树的权重总和。

数据范围

• $1 \le T \le 10^4$
• $2 \le N \le 2 \cdot 10^5$
• $(N - 1) \le M \le 2 \cdot 10^5$
• $S_i \in \{0, 1\}$
• $|S| = N$
• 存在至少一个 $i$ 使得 $S_i = 1$
• $1 \le u, v \le N$
• $u \neq v$
• 所有 $M$ 对 $(u, v)$ 均不相同。
• 给定的图 $G$ 是连通的。
• $N$ 的总和与 $M$ 的总和均不超过 $2 \cdot 10^5$。

样例

输入 1

7
3 3
101
1 2
2 3
1 3
6 5
100101
1 2
2 3
3 4
3 5
5 6
4 3
0111
1 2
1 3
1 4
7 7
1110111
1 7
1 4
2 4
3 4
4 5
4 6
4 7
2 1
1 0
1 2
6 9
100111
2 5
4 3
3 5
5 1
1 6
4 2
4 5
6 3
2 3
6 8
110110
3 5
4 2
2 6
5 1
1 6
6 4
4 3
4 5

输出 1

1
6
4
9
0
3
3

说明

测试用例 1：有 2 个标记节点 1 和 3。$\text{dist}(1, 3) = 1$，因为存在一条直接边 $(1, 3)$。因此，最小生成树的权重为 1。

测试用例 2：有 3 个标记节点 1、4 和 6。各边的权重如下： $\text{dist}(1, 4) = 3$ $\text{dist}(1, 6) = 4$ * $\text{dist}(4, 6) = 3$

最小生成树包含第 1 条边和第 3 条边。因此，权重总和为 6。