构造好路径

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图。(没有重边和自环的图称为简单图。)

对 $i = 1, 2, \ldots, M$,第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

当序列 $(A_1, A_2, \ldots, A_k)$ 满足以下两个条件时,称其为长度为 $k$ 的路径:

• 对所有 $i = 1, 2, \dots, k$,有 $1 \le A_i \le N$。
• 对所有 $i = 1, 2, \ldots, k-1$,顶点 $A_i$ 和顶点 $A_{i+1}$ 之间有边直接相连。

空序列视为长度为 $0$ 的路径。

给定一个长度为 $N$、由 $0$ 和 $1$ 组成的字符串 $S = s_1s_2\ldots s_N$。 当路径 $A = (A_1, A_2, \ldots, A_k)$ 满足以下条件时,称其为关于 $S$ 的好路径:

• 对所有 $i = 1, 2, \ldots, N$,有:
  • 若 $s_i = 0$,则 $A$ 中出现 $i$ 的次数为偶数。
  • 若 $s_i = 1$,则 $A$ 中出现 $i$ 的次数为奇数。

在本题的数据范围下,可以证明:至少存在一条长度不超过 $4N$ 的关于 $S$ 的好路径。 请输出一条长度不超过 $4N$ 的关于 $S$ 的好路径。

输入格式

输入按以下格式从标准输入给出:

N M
u_1 v_1
u_2 v_2
⋮
u_M v_M
S

输出格式

按以下格式输出一条长度不超过 $4N$ 的关于 $S$ 的好路径。 具体来说,第一行输出路径的长度 $K$,第二行用空格隔开输出路径的各元素。

K
A_1 A_2 … A_K

样例

6 6
6 3
2 5
4 2
1 3
6 5
3 2
110001

9
2 5 6 5 6 3 1 3 6

路径 $(2, 5, 6, 5, 6, 3, 1, 3, 6)$ 的长度不超过 $4N$,并且:

• 1 出现奇数次($1$ 次)
• 2 出现奇数次($1$ 次)
• 3 出现偶数次($2$ 次)
• 4 出现偶数次($0$ 次)
• 5 出现偶数次($2$ 次)
• 6 出现奇数次($3$ 次)

因此它是关于 $S = 110001$ 的好路径。

3 3
3 1
3 2
1 2
000

0

空路径 $()$ 是关于 $S = 000$ 的好路径。 此外,像 $(1, 2, 3, 1, 2, 3)$ 这样的路径也符合要求。

数据范围

• $2 \le N \le 10^5$
• $N-1 \le M \le \min\lbrace 2 \times 10^5, \frac{N(N-1)}{2}\rbrace$
• $1 \le u_i, v_i \le N$
• 给定的图是简单且连通的。
• $N$, $M$, $u_i$, $v_i$ 是整数。
• $S$ 是由 $0$ 和 $1$ 组成的长度为 $N$ 的字符串。

提示

答案不唯一,输出任意合法解即可。