AT_KeioPC2025_i Odd Even Partition

给定一个有 $N$ 个顶点 $M$ 条边的简单无向图，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 同时给你一个由 `X`、`Y`、`?` 组成的长度为 $N$ 的字符串 $S$。 请判断是否存在一组顶点集合对 $(X, Y)$，满足以下条件，并在存在时给出其中一组解。 - 每个顶点 $i~(1 \leq i \leq N)$ 只属于 $X, Y$ 中的一个； - $X$ 所诱导的子图中，每个顶点的度数都是奇数； - $Y$ 所诱导的子图中，每个顶点的度数都是偶数； - 若 $S_i = $ `X`，则顶点 $i$ 必须属于 $X$；$S_i = $ `Y` 时顶点 $i$ 必须属于 $Y$。 这里，诱导子图指在图 $G$ 上，顶点集合为 $S$ 的所有顶点，边集合为「$G$ 中两端都属于 $S$ 的所有边」的那张图。

输入按以下格式从标准输入读取。 > $N ~ M$ > $u_1 ~ v_1$ > $\vdots$ > $u_M ~ v_M$ > $S$

如果不存在满足条件的 $(X, Y)$，请输出 `-1`。 如果存在满足条件的解，请输出一个长度为 $N$ 的字符串 $T$，满足： - 若顶点 $i$ 属于 $X$，则 $T_i$ 等于 `X`；属于 $Y$ 时 $T_i$ 等于 `Y`。 若有多个解，输出任意一个均可。

### 部分分数 本题设有部分分数。 - 若 $S$ 中的 `?` 个数不超过 $17$，并答对该组数据，可得 $1$ 分。 ### 样例解释 1 令 $X = \{1, 2\}, Y = \{3\}$。 集合 $X$ 的诱导子图只包含一条边 $(1, 2)$，所以 $1, 2$ 的度数为 $1$。 集合 $Y$ 的诱导子图中无边，因此 $3$ 的度数为 $0$。 因此满足所有条件。你也可以输出 `YXX`。 # 数据范围 - $1 \leq N \leq 500$ - $0 \leq M \leq N(N-1)/2$ - $1 \leq u_i, v_i \leq N$ - 所给图为简单图 - $N, M, u_i, v_i$ 均为整数 - $S$ 为由 `X`、`Y`、`?` 组成的长度为 $N$ 的字符串 由 ChatGPT 5 翻译