← 返回题目列表

AtCoder · agc076_c

C. 史莱姆吃史莱姆

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

有 N 史莱姆编号自 1 to N。 每个史莱姆的颜色由一个介于 0 和 2K (含),以及史莱姆的颜色 i is 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 从场上消失。 另外,除了 u 与史莱姆有友谊 v 与史莱姆成为朋友 u (如果他们已经是史莱姆的朋友 u,什么也没发生)。

确定是否可以只留下史莱姆 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)
  • 对于任意两个史莱姆,一个可以通过遵循友谊关系到达另一个。
  • 总和 一个输入文件中的 N 超过 T 例最多 250000.
  • 总和 一个输入文件中的 M 超过 T 例最多 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- 第行应包含 Yes 如果可以只留下粘液 1 在球场上 i第一个案例,以及 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 在现场通过以下程序进行:

  • 选择 (u,v)=(3,2) 然后让史莱姆 3 吃史莱姆 2。史莱姆 2 消失,并且史莱姆 1 和 3 成为朋友。
  • 选择 (u,v)=(1,3) 然后让史莱姆 1 吃史莱姆 3。史莱姆 3 消失。