Extra Transition

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:

Input

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) \ne (a_\ell, b_\ell)\) for all \(k \ne \ell\)).

The input guarantees that the transition network is connected; for any levels \(i\) and \(j\) (\(i \ne 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\).

Output

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

Explanation for the sample input/output #1

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\).