← 返回题目列表

AtCoder · agc027_c

C. ABland 院子

中文机器翻译题面 查看原题

分数: 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 A or B.
  • 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.
77e96cf8e213d606ddd8f3c3f8315d32.png

示例输入 2

4 3
ABAB
1 2
2 3
3 1

示例输出 2

No
  • 例如,Nusook 无法使 BB.
  • 给定的图形可能未连接。
1ab1411cb9d6ee023d14ca4e77c4b584.png

示例输入 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