C - Slime Eat Slime Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 1200 点

問題文

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 ケースを解いてください．

制約

  • 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 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

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 を出力せよ．

入力例 1

4
2 1 1
0 0
1 2
3 2 1
0 2 1
1 2
2 3
6 6 1
0 0 1 2 1 0
1 2
2 3
3 4
4 5
5 6
1 6
5 4 2
2 4 3 2 1
1 2
2 4
2 5
3 5

出力例 1

No
Yes
No
No

1 つ目のテストケースでは，操作を 1 回も行うことができません．

2 つ目のテストケースでは，以下の手順でスライム 1 だけを場に残すことができます．

  • (u,v)=(3,2) と選び，スライム 3 にスライム 2 を食べさせる．スライム 2 が消え，スライム 1 とスライム 3 が友達になる．
  • (u,v)=(1,3) と選び，スライム 1 にスライム 3 を食べさせる．スライム 3 が消える．

Score : 1200 points

Problem Statement

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.

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.

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

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 Input 1

4
2 1 1
0 0
1 2
3 2 1
0 2 1
1 2
2 3
6 6 1
0 0 1 2 1 0
1 2
2 3
3 4
4 5
5 6
1 6
5 4 2
2 4 3 2 1
1 2
2 4
2 5
3 5

Sample Output 1

No
Yes
No
No

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.