AT_abc456_e.Endless Holidays

The Kingdom of AtCoder has $N$ cities, called city $1,2,\dots,N$. There are $M$ bidirectional roads connecting pairs of cities, where the $i$-th road connects cities $U_i$ and $V_i$. Any pair of cities can be reached from each other by traversing some roads.

In the Kingdom of AtCoder, a week consists of $W$ days. A week proceeds through days $1,2,\dots,W$, and the day after day $W$ is day $1$.

Each city has certain days of the week that are holidays. The holiday information for city $i$ is given as a string $S_i$ of length $W$: if the $j$-th character of $S_i$ is o, day $j$ is a holiday; if it is x, day $j$ is a weekday.

Takahashi chooses a city he likes and visits it at noon on day $1$. Each night thereafter, he repeatedly chooses to either stay in his current city or move to a city directly connected by a road. Output Yes if it is possible for him to keep moving so that the city he is in at noon every day is a holiday, and No otherwise.

$T$ test cases are given; solve each of them.

AtCoder 王国有 $N$ 座城市，编号为城市 $1,2,\dots,N$。有 $M$ 条双向道路连接若干对城市，其中第 $i$ 条道路连接城市 $U_i$ 和 $V_i$。任意两座城市之间均可通过若干条道路相互到达。

在 AtCoder 王国中，一周包含 $W$ 天。一周按天数 $1,2,\dots,W$ 顺序进行，第 $W$ 天之后是第 $1$ 天。

每座城市都有某些星期几被设为假日。城市 $i$ 的假日信息以一个长度为 $W$ 的字符串 $S_i$ 给出：若 $S_i$ 的第 $j$ 个字符为 o，则第 $j$ 天为假日；若为 x，则为工作日。

高桥选择一座他喜欢的城市，并于第 $1$ 天中午抵达该城市。此后每个夜晚，他重复执行如下操作：要么留在当前城市，要么沿一条道路移动至一个相邻城市。若存在一种移动方式，使得他在每天中午所处的城市均为当日的假日，则输出 Yes；否则输出 No。

共给出 $T$ 组测试数据，请对每组数据求解。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Here, $\mathrm{case}_i$ denotes the input for the $i$-th test case. Each test case is given in the following format:

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$
$W$
$S_1$
$S_2$
$\vdots$
$S_N$

输入从标准输入中按以下格式给出：

$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$

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, for example, the condition can be satisfied by repeatedly moving along cities $4 \to 2 \to 1 \to 4 \to 2 \to 1 \to \cdots$. Alternatively, the condition can also be satisfied by repeatedly moving along cities $3 \to 2 \to 3 \to 3 \to 2 \to 3 \to \cdots$.

For the second test case, the condition can be satisfied by staying in city $1$ indefinitely.

For the third test case, it is impossible to keep moving while satisfying the condition.

Constraints

• $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$
• Any pair of cities can be reached from each other by traversing some roads.
• $2 \leq W \leq 10$
• $T,N,M,U_i,V_i,W$ are integers.
• $S_i$ is a string of length $W$ consisting of o, x.
• The sum of $N$ over all test cases is at most $10^5$.
• The sum of $M$ over all test cases is at most $10^5$.

样例 1 解释：
对于第一个测试用例，例如，可通过反复沿城市序列 $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$ 来满足条件。

对于第三个测试用例，无法在持续移动的同时满足条件。

约束条件

• $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$。