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. $$$$$$

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

Output

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

Note

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$$$.

Extra Transition

Examples