問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。i 番目の辺は頂点 u_i と 頂点 v_i を結んでいます。

また、X, Y, ? からなる長さ N の文字列 S も与えられます。

頂点集合の部分集合の組 ( X, Y) のうち、以下の条件を満たすものが存在するか判定し、存在する場合一つ求めてください。

• 頂点 i ~ ( 1 \le i \le N ) は X, Y のうち片方にのみ含まれる。
• X による誘導部分グラフにおいて、すべての頂点の次数は奇数である。
• Y による誘導部分グラフにおいて、すべての頂点の次数は偶数である。
• S_i = X ならば頂点 i は X に、S_i = Y ならば頂点 i は Y に属している。

制約

• 1 \le N \le 500
• 0 \le M \le N (N - 1) / 2
• 1 \le u_i, v_i \le N
• 与えられるグラフは単純
• N, M, u_i, v_i はすべて整数
• S は X, Y, ? からなる長さ N の文字列

部分点

この問題には部分点が設定されている。

• S に含まれる ? の個数が 17 個以下であるデータセットに正解した場合 1 点が与えられる。

入力例 1

3 2
1 2
2 3
???

出力例 1

XXY

X = \{ 1, 2 \} , Y = \{ 3 \} とします。
集合 X の部分誘導グラフには、辺 (1, 2) のみが含まれます。よって、頂点 1, 2 の次数はともに 1 です。
集合 Y の部分誘導グラフには、辺が含まれません。よって、頂点 3 の次数は 0 です。
よって、これは条件を満たします。また YXX を出力しても正解となります。

入力例 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4
XXX?

出力例 2

XXXX

入力例 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4
YYYY

出力例 3

-1

入力例 4

10 11
1 5
2 3
2 10
3 6
3 7
4 5
4 9
5 8
6 7
6 10
8 9
?XY??YY???

出力例 4

XXYXXYYXYX