← 返回题目列表

AtCoder · abc456_e

E. 无尽的假期

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

分数: 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 无限期。

对于第三个测试用例,在满足条件的情况下不可能继续移动。