分数: 450 点
问题陈述
AtCoder王国有 N 城市,称为城市 1,2,\dots,N。 有 M 连接两座城市的双向道路,其中 i第条路连接城市 U_i 和 V_i。 任何一对城市都可以通过一些道路到达。
在AtCoder王国,一周包括 W 天。 一周经过几天 1,2,\dots,W,日复一日 W 是一天 1.
每个城市每周都有特定的几天是假期。
城市节假日信息 i 作为字符串给出 S_i 长度 W:如果 j- 第一个字符 S_i is o,日 j 是假期;如果是的话 x,日 j 是工作日。
高桥选择自己喜欢的城市并在当天中午游览 1。
此后的每天晚上,他都会反复选择要么留在现在的城市,要么搬到有公路直接相连的城市。
输出 Yes 如果他可以继续移动,让他每天中午所在的城市都是假期,并且 No 否则。
T 给出了测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^5
- N-1 \leq M \leq 10^5
- 1 \leq U_i \lt V_i \leq N
- 任何一对城市都可以通过穿过一些道路到达。
- 2 \leq W \leq 10
- T,N,M,U_i,V_i,W 是整数。
- S_i 是一个长度为的字符串 W 组成
o,x. - 总和 N 所有测试用例最多 10^5.
- 总和 M 所有测试用例最多 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i 表示输入 i- 第一个测试用例。每个测试用例均按以下格式给出:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M W S_1 S_2 \vdots S_N
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 4 4 1 2 1 4 2 4 2 3 3 xxo xox oxo oxx 1 0 4 oooo 5 5 1 4 2 3 4 5 3 4 2 5 7 oxxxxxx xxoxxxo xxxoxox xoxxoxx oxxxoxx
示例输出 1
Yes Yes No
以第一个测试用例为例,沿着城市重复移动即可满足条件 4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \cdots。 或者,也可以通过沿着城市反复移动来满足条件 3 \to 2 \to 3 \to 3 \to 2 \to 3 \to \cdots.
对于第二个测试用例,留在城市即可满足条件 1 无限期。
对于第三个测试用例,在满足条件的情况下不可能继续移动。