AT_KeioPC2025_i Odd Even Partition

頂点に $ 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 $ に属している。 誘導部分グラフとは $ S $ をグラフ $ G $ の頂点の部分集合とします。このとき、 $ G $ の $ S $ による誘導部分グラフとは、頂点集合が $ S $ で、辺集合が「 $ G $ の辺であって両端が $ S $ に含まれるものすべて」であるようなグラフです。

入力は以下の形式で標準入力から与えられる。 > $ N ~ M $ $ u_1 ~ v_1 $ $ \vdots $ $ u_M ~ v_M $ $ S $

条件を満たす $ (X, Y) $ が存在しないならば `-1` を出力せよ。条件を満たす解が存在するならば、そのうち一つを以下の形式で出力せよ。 > $ T $ ただし $ T $ は長さ $ N $ の文字列で、以下を満たす必要がある。 - $ T_i $ は頂点 $ i $ が $ X $ に属している場合 `X`、 $ Y $ に属している場合 `Y` である。 条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。

### 部分点 この問題には部分点が設定されている。 - $ S $ に含まれる `?` の個数が $ 17 $ 個以下であるデータセットに正解した場合 $ 1 $ 点が与えられる。 ### Sample Explanation 1 $ X = \{ 1, 2 \} , Y = \{ 3 \} $ とします。 集合 $ X $ の部分誘導グラフには、辺 $ (1, 2) $ のみが含まれます。よって、頂点 $ 1, 2 $ の次数はともに $ 1 $ です。 集合 $ Y $ の部分誘導グラフには、辺が含まれません。よって、頂点 $ 3 $ の次数は $ 0 $ です。 よって、これは条件を満たします。また `YXX` を出力しても正解となります。 ### Constraints - $ 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 $ の文字列