分数: 600 点
问题陈述
给你一个简单的连通无向图 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 \leq A_i \leq N.
- 对于所有人 i = 1, 2, \ldots, k-1,顶点 A_i 和顶点 A_{i+1} 直接与边缘连接。
空序列被视为长度路径 0.
你被蜇了 S = s_1s_2\ldots s_N 长度 N 组成 0 和 1。 一条路 A = (A_1, A_2, \ldots, A_k) 据说是 好路 关于 S 如果满足以下条件:
- 对于所有人 i = 1, 2, \ldots, N,认为:
- if s_i = 0,那么 A 有偶数个 i的。
- if s_i = 1,那么 A 有奇数个 i的。
在该问题的约束下,可以证明至少存在一条关于 最多 S 长度 4N。 打印一条关于以下方面的良好路径 S 长度 4N.
约束
- 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 是一个长度为 N 组成 0 和 1.
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M S
输出
打印一条关于的好路径 S 长度 4N 采用以下格式。 具体来说,第一行应包含长度 K 路径,第二行应包含路径的元素,中间有空格。
K A_1 A_2 \ldots A_K
示例输入 1
6 6 6 3 2 5 4 2 1 3 6 5 3 2 110001
示例输出 1
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.
示例输入 2
3 3 3 1 3 2 1 2 000
示例输出 2
0
空路径 () 是一条很好的路径 S = 000000。 或者,像这样的路径 (1, 2, 3, 1, 2, 3) 也被接受。