AT_agc076_c [AGC076C] Slime Eat Slime

There are $ N $ slimes numbered from $ 1 $ to $ N $ . The color of each slime is represented by an integer between $ 0 $ and $ 2K $ (inclusive), and the color of slime $ i $ is $ C_i $ . Currently, $ M $ pairs of slimes are in a (bidirectional) friendship. Specifically, slimes $ A_i $ and $ B_i $ are friends ( $ 1 \leq i \leq M $ ). Here, it is guaranteed that for any two slimes, one can reach the other by following friendship relations. You can perform the following operation: - First, choose a pair of slimes $ (u,v) $ that satisfies both of the following conditions: - Slimes $ u $ and $ v $ are in a friendship. - $ (C_u - C_v) \bmod (2K+1) \geq K+1 $ (here, the result of $ x \bmod y $ is always in the range $ [0,y-1] $ ). - Then, let slime $ u $ eat slime $ v $ . Slime $ v $ disappears from the field. Also, all slimes except $ u $ that were in a friendship with slime $ v $ become friends with slime $ u $ (if they were already friends with slime $ u $ , nothing happens). Determine whether it is possible to leave only slime $ 1 $ on the field by repeating the operation appropriately. Solve $ T $ cases for one input.

The input is given from Standard Input in the following format: > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ Each test case is given in the following format: > $ N $ $ M $ $ K $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

Output $ T $ lines. The $ i $ -th line should contain `Yes` if it is possible to leave only slime $ 1 $ on the field for the $ i $ -th case, and `No` otherwise.

### Sample Explanation 1 In the first test case, no operation can be performed. In the second test case, it is possible to leave only slime $ 1 $ on the field by the following procedure: - Choose $ (u,v)=(3,2) $ and let slime $ 3 $ eat slime $ 2 $ . Slime $ 2 $ disappears, and slimes $ 1 $ and $ 3 $ become friends. - Choose $ (u,v)=(1,3) $ and let slime $ 1 $ eat slime $ 3 $ . Slime $ 3 $ disappears. ### Constraints - $ 1 \leq T \leq 125000 $ - $ 2 \leq N \leq 250000 $ - $ N-1 \leq M \leq 250000 $ - $ 1 \leq K \leq N $ - $ 0 \leq C_i \leq 2K $ - $ 1 \leq A_i < B_i \leq N $ - $ (A_i,B_i) \neq (A_j,B_j) $ ( $ i \neq j $ ) - For any two slimes, one can reach the other by following friendship relations. - The sum of $ N $ over the $ T $ cases is at most $ 250000 $ . - The sum of $ M $ over the $ T $ cases is at most $ 250000 $ . - All input values are integers.