AT_abc456_e [ABC456E] Endless Holidays

AtCoder 王国有 $N$ 个城市，分别编号为 $1, 2, \dots, N$。有 $M$ 条双向道路连接着若干城市，第 $i$ 条道路连接城市 $U_i$ 和 $V_i$。任意两个城市之间都可以通过若干条道路互达。 在 AtCoder 王国，一周共有 $W$ 天，分别为第 $1, 2, \dots, W$ 天，第 $W$ 天的下一天又是第 $1$ 天。 每个城市在一周的不同天会有不同的休息日。城市 $i$ 是否在一周的第 $j$ 天为休息日，用长度为 $W$ 的字符串 $S_i$ 描述：若 $S_i$ 的第 $j$ 个字符为 `o`，则第 $j$ 天是休息日；若为 `x`，则该天为工作日。 高桥会选择一个喜欢的城市，并于第 $1$ 天中午到达。每晚之后，他可以选择留在当前城市，或移动到一个与当前城市有直接道路相连的城市。请输出是否存在一种移动方式，使得高桥每天中午所在的城市均为休息日。如果可以，输出 `Yes`，否则输出 `No`。 共给出 $T$ 组测试数据，请分别作答。

输入从标准输入读入，格式如下： > $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 对于第一组测试数据，例如可以沿城市 $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 < 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$ 由 ChatGPT 5 翻译