分数: 900 点
问题陈述
给你一个无向图,包括 N 顶点和 M 边缘。
顶点已编号 1 to N,并且边缘已编号 1 to M。
另外,每个顶点都有一个标签, A or B。顶点的标签 i is s_i。
边缘 i 双向连接顶点 a_i 和 b_i.
怪盗Nusook喜欢选择某个顶点作为起点,并遍历一条边零次或多次。 今天,他将在如上所述旅行后创建一个字符串,从起点开始,按照访问的顺序放置访问过的顶点的标签。
例如,在图中,顶点 1 有标签 A 和顶点 2 有标签 B,如果 Nusook 沿着路径行进 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2,结果字符串是 ABABB.
确定 Nusook 是否可以使所有字符串组成 A 和 B.
约束
- 2 \leq N \leq 2 \times 10^{5}
- 1 \leq M \leq 2 \times 10^{5}
- |s| = N
- s_i is
AorB. - 1 \leq a_i, b_i \leq N
- 给定的图形可能不是简单的或连通的。
输入
输入由标准输入按以下格式给出:
N M
s
a_1 b_1
:
a_{M} b_{M}
输出
如果 Nusook 可以使所有字符串组成 A 和 B,打印 Yes;否则,打印 No.
示例输入 1
2 3 AB 1 1 1 2 2 2
示例输出 1
Yes
- 由于 Nusook 可以访问 Vertex 1 和顶点 2 以他喜欢的任何方式,他可以使所有字符串组成
A和B.
示例输入 2
4 3 ABAB 1 2 2 3 3 1
示例输出 2
No
- 例如,Nusook 无法使
BB. - 给定的图形可能未连接。
示例输入 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
示例输出 3
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
示例输出 4
No