← 返回题目列表

AtCoder · KeioPC2025_i

I. 奇偶分区

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

配点 : 101 点

問題文

在顶部 编号为 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 。
子集 <var>\( - 满足<var>1 \le i \le N</var>的整数<var>i</var>仅包含在<var>X、Y</var>之一中。 - 在顶点集为<var>X</var>的导出子图中,所有顶点的度都是奇数。 - 在顶点集为<var>Y</var>的导出子图中,所有顶点的度都是偶数。 - 如果<var>S_i =</var> `X`,<var>i</var>属于<var>X</var>,如果<var>S_i =</var> `Y`,<var>i</var>属于<var>Y</var>。
什么是诱导子图? 图 S 令 为 G 顶点的子集。这时,G 的 S 的引导子图是其顶点集为 S ,边缘集是``G 两端有边 这是一张“ S 中包含的所有内容”的图表。

制約

  • 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 点。

入力

输入是按以下格式从标准输入给出的。

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 。

如果有多个解满足条件,则任何一个输出都将被视为正确答案。


入力例 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