你正在开发一款包含 $n$ 个关卡的游戏，关卡编号为 $1$ 到 $n$。关卡之间通过一个由 $m$ 条通道组成的通道网络相连，通道编号为 $1$ 到 $m$。通道 $k$ 双向连接关卡 $a_k$ 和 $b_k$（$1 \le k \le m$）。

单次游戏从关卡 $1$ 开始。每当玩家进入一个新关卡时，玩家必须通关该关卡，然后移动到另一个与其直接通过通道相连且在本次游戏中尚未通关的关卡。当关卡 $n$ 被通关时，游戏成功结束。

如果玩家可以在单次游戏中按照某个序列给出的顺序依次通关这些关卡，则一个由两两不同的关卡组成、以关卡 $1$ 开始并以关卡 $n$ 结束的序列被称为一条成功路径。

如果一个通道网络满足以下两个条件，则称其是设计良好的：

• 对于任意关卡 $i$（$2 \le i \le n - 1$），存在一条包含关卡 $i$ 的成功路径。

• 对于任意一对关卡 $i$ 和 $j$（$2 \le i < j \le n - 1$），以下两个条件中至多有一个成立：

  • 存在一条包含关卡 $i$ 和 $j$ 的成功路径，且关卡 $i$ 在关卡 $j$ 之前出现。
  • 存在一条包含关卡 $i$ 和 $j$ 的成功路径，且关卡 $j$ 在关卡 $i$ 之前出现。

你的第一个任务是判断给定的通道网络是否设计良好。

如果网络设计良好，你还有第二个任务。设 $S$ 为满足以下条件的整数对 $(i, j)$（$1 \le i < j \le n$）的集合：关卡 $i$ 和 $j$ 之间没有直接相连的通道，且在它们之间添加一条双向额外通道后，网络仍然保持设计良好。你对集合 $S$ 感兴趣。给你一个长度为 $n$ 的整数序列 $w_1, \dots, w_n$。作为 $S$ 的摘要，请计算以下总和：

$$\sum_{(i,j) \in S} w_i w_j$$

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 50\,000$），表示测试用例的数量。接下来是 $t$ 个测试用例，每个测试用例的格式如下。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 200\,000$；$n - 1 \le m \le 200\,000$）。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（对于所有 $i$，有 $1 \le w_i \le 5000$）。

接下来的 $m$ 行中，第 $k$ 行包含两个整数 $a_k$ 和 $b_k$（$1 \le a_k < b_k \le n$；对于所有 $k \ne \ell$，有 $(a_k, b_k) \ne (a_\ell, b_\ell)$）。

输入保证通道网络是连通的；即对于任意关卡 $i$ 和 $j$（$i \ne j$），都存在一条连接关卡 $i$ 和关卡 $j$ 的通道序列。

单个输入文件中所有测试用例的 $n$ 之和不超过 $200\,000$。

单个输入文件中所有测试用例的 $m$ 之和不超过 $200\,000$。

输出格式

对于每个测试用例，如果通道网络不是设计良好的，输出 bad。否则，输出上述定义的总和。

样例

输入样例 1

3
4 4
1 2 3 4
1 2
1 3
2 4
3 4
3 2
2026 3 9
1 3
2 3
10 11
15 51 82 49 1 55 45 5 25 91
7 10
1 6
2 5
4 7
3 8
1 9
4 6
2 10
3 9
5 9
2 8

输出样例 1

4
bad
23336

说明

样例解释 1

对于第一个测试用例，给定的通道网络是设计良好的。添加额外通道 $(i, j)$ 的可能候选对为 $(1, 4)$ 和 $(2, 3)$。

• 对于 $(1, 4)$，在它们之间添加通道可以使网络保持设计良好。
• 另一方面，对于 $(2, 3)$，在它们之间添加通道不能使网络保持设计良好。此时存在两条成功路径 $(1, 2, 3, 4)$ 和 $(1, 3, 2, 4)$。关卡对 $2$ 和 $3$ 不满足第二个条件。

因此，答案为 $w_1 w_4 = 1 \times 4 = 4$。

对于第二个测试用例，给定的通道网络不是设计良好的，因为不存在包含关卡 $2$ 的成功路径。