CF2206G 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: $$$ \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.

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