#216599. [ICPC 2026 APC] Extra Transition

You are developing a game consisting of levels, numbered from to . Levels are connected by a transition network consisting of transitions, numbered from to . Transition connects levels and bidirectionally ( ).

A single run of the game starts at level . 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 is completed.

A sequence of pairwise distinct levels starting from level and ending at level 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 ( ), there exists a successful path containing level .
• For any pair of levels and ( ), at most one of the following holds:
  • There exists a successful path containing levels and with level appearing before level .
  • There exists a successful path containing levels and with level appearing before level .

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 be the set of pairs of integers ( ) such that levels and are not directly connected and adding a bidirectional extra transition between them keeps the network well-designed. You are interested in the set . You are given a sequence of integers . As a summary of , compute the following sum:

The first line of input contains one integer ( ) representing the number of test cases. After that, test cases follow. Each of them is presented as follows.

The first line of each test case contains two integers and ( ; ).

The second line contains integers ( for all ).

The -th of the next lines contains two integers and ( ; for all ).

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

The sum of across all test cases in one input file does not exceed .

The sum of across all test cases in one input file does not exceed .

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

样例输入 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

For the first test case, the given transition network is well-designed. Possible candidates for adding extra transitions are and .

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

Thus, the answer is . For the second test case, the given transition network is not well-designed because there is no successful path containing level .