分数: 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 消失。