E : Oh, Vertexes & Edges!

背景

kagamiz 君は塗り $x$ - $y$ 平面が大好きです. しかし塗り $x$ - $y$ 平面をしすぎてもう普通の塗り $x$ - $y$ 平面では満足できない体になってしまいました.

kagamiz「これはもうグラフを塗るしかないみたいですね…」

問題

$N$ 頂点 $M$ 辺の無向単純グラフ $G$ が与えられる. 単純グラフとは自己ループや多重辺が存在しないグラフを指す.

最初の状態では, $G$ の幾つかの頂点は黒く塗られていて, 他の頂点は白く塗られている.

ある白い頂点 $v$ について, $v$ と黒く塗られた頂点のみで構成された閉路が存在すれば, $v$ を黒く塗ることが出来る.

上記の操作を好きな回数繰り返したとき, 全ての頂点について, その頂点を黒く塗ることができるかを調べよ.

入力

$N$ $S$ $M$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

頂点の最初の状態での色は長さ $N$ の文字列 $S$ で表され, $i$ 番目の頂点の色は $S_i = \text{'B'}$ であれば黒, $S_i = \text{'W'}$ であれば白である.

$G$ の辺はそれぞれ 2 つの整数 $X_i,\ Y_i$ で表され, これは $X_i$ 番目の頂点と $Y_i$ 番目の頂点の間に無向辺が存在することを表す.

出力

1 行に, $N$ 文字からなる文字列を出力せよ.

$i$ 文字目は, もし $i$ 番目の頂点を黒く塗ることができるなら B, 出来なければ W とせよ.

制約

全てのデータセットでは以下の制約を満たす.

• $1 \leqq N \leqq 100,000.$
• $0 \leqq M \leqq 100,000.$
• $1 \leqq X_i \lt Y_i \leqq N.$

また，この問題には部分点が設定されており，40 点分の入力データは追加で以下の制約を満たす.

• $1 \leqq N \leqq 50.$

入出力例

入力例 1

4
BBWW
5
1 2
1 3
2 3
1 4
3 4

出力例 1

BBBB

3 番目の頂点を黒く塗ることができ, 3 番目の頂点を黒く塗ると次に 4 番目の頂点を黒く塗ることができます.

入力例 2

7
WWBWBBW
0

出力例 2

WWBWBBW

入力例 3

4
WWWW
6
1 2
1 3
1 4
2 3
2 4
3 4

出力例 3

WWWW

入力例 4

9
BWWBWWWBW
11
1 2
1 3
2 3
4 8
4 9
4 7
6 7
5 6
4 5
7 9
8 9

出力例 4

BWWBWWBBB

入力例 5

10
BWWWBWWWBB
9
2 6
3 6
2 3
2 10
1 2
1 10
3 9
3 5
5 9

出力例 5

BBBWBBWWBB