题目描述

You are developing a game consisting of $n$ levels, numbered from $1$ to $n$ . Levels are connected by a transition network consisting of $m$ transitions, numbered from $1$ to $m$ . Transition $k$ connects levels $a_k$ and $b_k$ bidirectionally ( $1 \le k \le m$ ).

A single run of the game starts at level $1$ . Each time a player enters a new level, the player must complete it and then move to another level that is directly connected by a transition and has not been completed in the run. The run ends successfully when level $n$ is completed.

A sequence of pairwise distinct levels starting from level $1$ and ending at level $n$ is called a successful path if a player can complete the levels in the order given by the sequence in a single run.

A transition network is well-designed if it satisfies both of the following:

• For any level $i$ ( $2 \le i \le n-1$ ), there exists a successful path containing level $i$ .
• For any pair of levels $i$ and $j$ ( $2 \le i \lt j \le n-1$ ), at most one of the following holds:
  • There exists a successful path containing levels $i$ and $j$ with level $i$ appearing before level $j$ .
  • There exists a successful path containing levels $i$ and $j$ with level $j$ appearing before level $i$ .

Your first task is to determine whether the given transition network is well-designed or not.

If the network is well-designed, you have a second task. Let $S$ be the set of pairs of integers $(i, j)$ ( $1 \le i \lt j \le n$ ) such that levels $i$ and $j$ are not directly connected and adding a bidirectional extra transition between them keeps the network well-designed. You are interested in the set $S$ . You are given a sequence of $n$ integers $w_1, \ldots, w_n$ . As a summary of $S$ , compute the following sum:

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

输入格式

The first line of input contains one integer $t$ ( $1 \le t \le 50\,000$ ) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of each test case contains two integers $n$ and $m$ ( $3 \le n \le 200\,000$ ; $n - 1 \le m \le 200\,000$ ).

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ( $1 \le w_i \le 5000$ for all $i$ ).

The $k$ -th of the next $m$ lines contains two integers $a_k$ and $b_k$ ( $1 \le a_k \lt b_k \le n$ ; $(a_k, b_k) \not= (a_\ell, b_\ell)$ for all $k \not= \ell$ ).

The input guarantees that the transition network is connected; for any levels $i$ and $j$ ( $i \not= j$ ), there exists a sequence of transitions leading from level $i$ to level $j$ .

The sum of $n$ across all test cases in one input file does not exceed $200\,000$ .

The sum of $m$ across all test cases in one input file does not exceed $200\,000$ .

输出格式

For each test case, if the transition network is not well-designed, output bad. Otherwise, output the sum defined above.

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

4
bad
23336

提示

For the first test case, the given transition network is well-designed. Possible candidates for adding extra transitions $(i, j)$ are $(1, 4)$ and $(2, 3)$ .

• For $(1, 4)$ , adding a transition between them keeps the network well-designed.
• For $(2, 3)$ , on the other hand, adding a transition between them does not keep the network well-designed. There exist two successful paths $(1, 2, 3, 4)$ and $(1, 3, 2, 4)$ . The second condition for the pair of levels $2$ and $3$ is not satisfied.

Thus, the answer is $w_1 w_4 = 1 \times 4 = 4$ . For the second test case, the given transition network is not well-designed because there is no successful path containing level $2$ .