给定一个有 $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 翻译