You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

这一切都是命运石之门的选择

Description

OR是一个疯狂科学家，有一天，助手给他出了一个问题。某个国家有 $N$ 座城市，编号为 $1, 2, \dots, N$。有 $M$ 条双向道路连接城市对，其中第 $i$ 条道路连接城市 $U_i$ 和 $V_i$。任意两座城市之间都可以通过若干条道路相互到达。

在这个国家内，一周有 $W$ 天。一周按天 $1, 2, \dots, W$ 的顺序进行，第 $W$ 天之后的下一天是第 $1$ 天。

每座城市都有特定的星期几是节假日。城市 $i$ 的节假日信息以长度为 $W$ 的字符串 $S_i$ 给出：

• 如果 $S_i$ 的第 $j$ 个字符是 o，则第 $j$ 天是节假日。
• 如果 $S_i$ 的第 $j$ 个字符是 x，则第 $j$ 天是工作日。

假设OR需要选择其中的一座城市，并在第 1 天的中午访问该城市。此后每晚，他反复选择留在当前城市或移动到由道路直接连接的城市。

如果他能够持续移动，使得每天中午所在的城市都是节假日，则OR要回答 Yes，否则回答 No。OR发现这个数据很大，没办法独立推理出问题的答案，请帮帮他。

共有 $T$ 个测试用例；请分别解决每个测试用例。

Format

Input

$输入由标准输入给出，格式如下$:

$T$

$\text{case}_1$

$\text{case}_2$

⋮

$\text{case}_T$

$这里对于每一个case$:

$N$ $M$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

$W$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

输出共 $T$ 行。第 i 行输出第 i 组测试数据的答案。

Samples

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

Yes
Yes
No

Limitation

3s, 1024 MiB for each test case.

$1 \le T \le 2 \times 10^5$, $2 \le N \le 2 \times 10^5$, $N-1 \leq M \leq 10^5$, $1 \leq U_i \lt V_i \leq N$, $1 \le W \le 10$, $S_i$ 是一个长度为 $W$ 的字符串，由 o 和 x 组成。给定的图是连通的。 所有输入值均为整数。