← 返回题目列表

AtCoder · abc244_g

G. 构建美好道路

中文机器翻译题面 查看原题

分数: 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) 也被接受。