题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。每个顶点除了编号外，还带有一个标签 A 或 B，顶点 $i$ 的标签为 $s_i$。

第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，且是双向的。

怪盗ヌ斯克喜欢从任意一个顶点出发，经过 $0$ 次或多次沿边移动。今天，他想在移动后，将访问过的顶点的标签，按照从起点开始访问的顺序排列，组成一个字符串。

例如，在一个顶点 $1$ 的标签为 A，顶点 $2$ 的标签为 B 的图中，如果ヌ斯克按照 $1\rightarrow2\rightarrow1\rightarrow2\rightarrow2$ 的顺序移动，则可以得到字符串 ABABB。

请判断怪盗ヌ斯克是否能够构造出任意由 A 和 B 组成的字符串。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $s$ $a_1$ $b_1$ $\cdots$ $a_M$ $b_M$

输出格式

如果ヌ斯克能够构造出任意由 A 和 B 组成的字符串，则输出 Yes，否则输出 No。

样例 1

输入

2 3
AB
1 1
1 2
2 2

输出

Yes

样例 2

输入

4 3
ABAB
1 2
2 3
3 1

输出

No

样例 3

输入

13 23
ABAAAABBBBAAB
7 1
10 6
1 11
2 10
2 8
2 11
11 12
8 3
7 12
11 2
13 13
11 9
4 1
9 7
9 6
8 13
8 6
4 10
8 7
4 3
2 1
8 12
6 9

输出

Yes

样例 4

输入

13 17
BBABBBAABABBA
7 1
7 9
11 12
3 9
11 9
2 1
11 5
12 11
10 8
1 11
1 8
7 7
9 10
8 8
8 12
6 2
13 11

输出

No

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^{5}$
• $1 \leq M \leq 2 \times 10^{5}$
• $|s| = N$
• $s_i$ 为 A 或 B
• $1 \leq a_i, b_i \leq N$
• 给定的图不一定是简单图，也不一定是连通图

样例解释 1

• ヌ斯克可以自由地访问顶点 $1$ 和顶点 $2$，因此可以构造出任意由 A 和 B 组成的字符串。

样例解释 2

• 例如，无法构造出 BB。给定的图不一定是连通图。

由 ChatGPT 4.1 翻译