题目描述

$N$ 頂点 $M$ 本の辺からなる無向グラフが与えられます。 頂点には $1$ から $N$ の番号が、辺には $1$ から $M$ の番号がついています。 頂点には番号以外に A か B のラベルがついており、頂点 $i$ には $s_i$ のラベルがついています。

辺 $i$ は頂点 $a_i$ と $b_i$ を双方向につなぐ辺です。

怪盗ヌスークは好きな頂点を始点として選び、そこから $0$ 回以上辺を辿って移動するのが好きです。 今日は移動後に、訪れた頂点についているラベルを始点から訪問した順に並べて文字列を作ることにしました。

例えば、頂点 $1$ にラベル A が、頂点 $2$ にラベル B がついているグラフにおいて、ヌスークが $ 1\ \rightarrow\ 2\ \rightarrow\ 1\ \rightarrow\ 2\ \rightarrow\ 2 $ と移動した場合、ABABB が作られます。

怪盗ヌスークが文字 A,B のみからなる任意の文字列が作れるかどうかを判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $s$ $a_1$ $b_1$ $:$ $a_{M}$ $b_{M}$

输出格式

ヌスークが文字 A,B のみからなる任意の文字列が作ることが可能なら Yes を、そうでなければ No を出力せよ。

题目大意

有一张无向图，每个点有一个标签。标签只可能是 $\texttt{A}$ 或者 $\texttt{B}$。每条路径都对应着一个字符串。对应方式如下：从起点开始，把经过的点的标签都记下来。
问是否任意由 $\texttt{A}$ 或者 $\texttt{B}$ 组成的字符串 $S$ 都存在一条原图中的路径（可以重复经过点和边）使得其对应的字符串是 $S$。

2 3
AB
1 1
1 2
2 2

Yes

4 3
ABAB
1 2
2 3
3 1

No

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

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$
• 与えられるグラフは単純とも連結とも限らない

Sample Explanation 1

- ヌスークは頂点 $1$ と頂点 $2$ を自由に訪れることができるため、A,B のみからなる任意の文字列が作ることが可能です 

Sample Explanation 2

- 例えば、BB を作ることができません - 与えられるグラフは連結とは限りません