AT_agc076_c [AGC076C] Slime Eat Slime

$ 1 $ から $ N $ までの番号のついた $ N $ 匹のスライムがいます． それぞれのスライムの色は $ 0 $ 以上 $ 2K $ 以下の整数で表され，スライム $ i $ の色は $ C_i $ です． 今， $ M $ 組のスライムが（双方向の）友達関係にあり，具体的にはスライム $ A_i $ とスライム $ B_i $ は友達です ( $ 1 \leq i \leq M $ )． ここで，どの $ 2 $ 匹のスライムについても，友達関係をたどることで一方から他方へ到達できることが保証されます． あなたは以下の操作を行うことができます． - まず，次の条件を両方とも満たすスライムの組 $ (u,v) $ を選ぶ． - スライム $ u,v $ は友達関係にある． - $ (C_u - C_v) \bmod (2K+1) \geq K+1 $ （なお， $ x \bmod y $ の結果は常に $ [0,y-1] $ の範囲に入るとする） - そして，スライム $ u $ にスライム $ v $ を食べさせる． ここでスライム $ v $ は場から消える． また，スライム $ v $ と友達関係にあった $ u $ 以外のすべてのスライムは，スライム $ u $ と友達になる（すでにスライム $ u $ と友達であった場合は何も起きない）． 適切に操作を繰り返すことでスライム $ 1 $ だけを場に残すことが可能かどうか判定してください． $ 1 $ つの入力につき， $ T $ ケースを解いてください．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ M $ $ K $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

$ T $ 行出力せよ． $ i $ 行目には， $ i $ ケース目においてスライム $ 1 $ だけを場に残すことが可能ならば `Yes`，不可能ならば `No` を出力せよ．

### Sample Explanation 1 $ 1 $ つ目のテストケースでは，操作を $ 1 $ 回も行うことができません． $ 2 $ つ目のテストケースでは，以下の手順でスライム $ 1 $ だけを場に残すことができます． - $ (u,v)=(3,2) $ と選び，スライム $ 3 $ にスライム $ 2 $ を食べさせる．スライム $ 2 $ が消え，スライム $ 1 $ とスライム $ 3 $ が友達になる． - $ (u,v)=(1,3) $ と選び，スライム $ 1 $ にスライム $ 3 $ を食べさせる．スライム $ 3 $ が消える． ### 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 $ ) - どの $ 2 $ 匹のスライムについても，友達関係をたどることで一方から他方へ到達できる - $ T $ ケースにわたる $ N $ の総和は $ 250000 $ 以下 - $ T $ ケースにわたる $ M $ の総和は $ 250000 $ 以下 - 入力はすべて整数