当前没有测试数据。

G - 构建好路径

得分：600分

问题描述

给定一个简单连通的无向图，有N个顶点和M条边。（如果一个图没有多重边或自环，则称其为简单图）
对于$i = 1, 2, \ldots, M$，第i条边连接了顶点$u_i$和$u_i$。

如果满足以下两个条件，则称$(A_1, A_2, \ldots, A_k)$为一个长度为k的路径：

• 对于所有$i = 1, 2, \dots, k$，有$1 \leq A_i \leq 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$的好路径。

约束

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

---

输入

从标准输入中按如下格式输入：

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$S$

输出

请按照如下格式输出一个长度不超过$4N$的相对于$S$的好路径。 具体地，第一行应该包含路径$K$的长度，第二行应该包含路径元素，中间用空格分隔。

``` $K$ $A_1$ $A_2$ $\ldots$ $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$
• 它包含奇数（$1$）个$2$
• 它包含偶数（$2$）个$3$
• 它包含偶数（$0$）个$4$
• 它包含偶数（$2$）个$5$
• 它包含奇数（$3$）个$6$

所以它是相对于$S = 110001$的一个好路径。

---

3 3
3 1
3 2
1 2
000

0

空路径$()$是相对于$S = 000000$的一个好路径。 另外，路径如$(1, 2, 3, 1, 2, 3)$也是可以的。