AT_agc076_c.[AGC076C] Slime Eat Slime

共有 $N$ 只史莱姆，编号从 $1$ 到 $N$。每只史莱姆的颜色由一个 $0$ 到 $2K$（包含端点）之间的整数表示，第 $i$ 只史莱姆的颜色为 $C_i$。

目前有 $M$ 对史莱姆存在互为好友的关系。具体来说，史莱姆 $A_i$ 与 $B_i$ 是好友（$1 \leq i \leq M$）。这里保证，对于任意两只史莱姆，通过一系列好友关系，总可以互相到达。

你可以进行如下操作：

• 首先，选择一对史莱姆 $(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$ 成为好友（如果已经是好友则不作任何处理）。

请判断能否通过若干次上述操作后，只让第 $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。

样例解释 1

在第一个测试点中，无法进行任何操作。

在第二个测试点中，可以通过以下方式只剩下第 $1$ 只史莱姆：

• 选择 $(u,v)=(3,2)$，让史莱姆 $3$ 吃掉史莱姆 $2$，此时史莱姆 $2$ 消失，史莱姆 $1$ 和 $3$ 成为好友。
• 选择 $(u,v)=(1,3)$，让史莱姆 $1$ 吃掉史莱姆 $3$，此时史莱姆 $3$ 消失。

数据范围

• $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$）
• 对于任意两只史莱姆，通过若干次好友关系都能互相到达。
• 所有 $T$ 组测试数据中 $N$ 的总和不超过 $250000$。
• 所有 $T$ 组测试数据中 $M$ 的总和不超过 $250000$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译