#abc244g. G - Construct Good Path

G - Construct Good Path

Score : 600600 points

问题描述

给定一个包含 NN 个顶点和 MM 条边的简单连通无向图。(如果图中没有重边且没有自环,则称该图为简单图。) 对于 i=1,2,,Mi = 1, 2, \ldots, M,第 ii 条边连接顶点 uiu_i 和顶点 viv_i

若满足以下两个条件,则称序列 (A1,A2,,Ak)(A_1, A_2, \ldots, A_k) 是一条长度为 kk路径

  • 对于所有 i=1,2,,ki = 1, 2, \dots, k,有 1AiN1 \leq A_i \leq N
  • 对于所有 i=1,2,,k1i = 1, 2, \ldots, k-1,顶点 AiA_i 和顶点 Ai+1A_{i+1} 直接通过一条边相连。

空序列被视为长度为 00 的路径。

给定一个由 0011 组成的长度为 NN 的字符串 S=s1s2sNS = s_1s_2\ldots s_N。若满足以下条件,则称路径 A=(A1,A2,,Ak)A = (A_1, A_2, \ldots, A_k) 对于 SS 是一条 好路径

  • 对于所有 i=1,2,,Ni = 1, 2, \ldots, N,满足:
    • si=0s_i = 0,则 AA 中包含偶数个 ii
    • si=1s_i = 1,则 AA 中包含奇数个 ii

根据本题的约束条件,可以证明存在至少一条长度不超过 4N4N 的对于 SS 的好路径。请打印出一条长度不超过 4N4N 的对于 SS 的好路径。

以上为通义千问 qwen-max 翻译,仅供参考。

Problem Statement

You are given a simple connected undirected graph with NN vertices and MM edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i=1,2,,Mi = 1, 2, \ldots, M, the ii-th edge connects Vertex uiu_i and Vertex viv_i.

A sequence (A1,A2,,Ak)(A_1, A_2, \ldots, A_k) is said to be a path of length kk if both of the following two conditions are satisfied:

  • For all i=1,2,,ki = 1, 2, \dots, k, it holds that 1AiN1 \leq A_i \leq N.
  • For all i=1,2,,k1i = 1, 2, \ldots, k-1, Vertex AiA_i and Vertex Ai+1A_{i+1} are directly connected with an edge.

An empty sequence is regarded as a path of length 00.

You are given a sting S=s1s2sNS = s_1s_2\ldots s_N of length NN consisting of 00 and 11. A path A=(A1,A2,,Ak)A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to SS if the following conditions are satisfied:

  • For all i=1,2,,Ni = 1, 2, \ldots, N, it holds that:
    • if si=0s_i = 0, then AA has even number of ii's.
    • if si=1s_i = 1, then AA has odd number of ii's.

Under the Constraints of this problem, it can be proved that there is at least one good path with respect to SS of length at most 4N4N. Print a good path with respect to SS of length at most 4N4N.

Constraints

  • 2N1052 \leq N \leq 10^5
  • $N-1 \leq M \leq \min\lbrace 2 \times 10^5, \frac{N(N-1)}{2}\rbrace$
  • 1ui,viN1 \leq u_i, v_i \leq N
  • The given graph is simple and connected.
  • N,M,uiN, M, u_i, and viv_i are integers.
  • SS is a string of length NN consisting of 00 and 11.

Input

Input is given from Standard Input in the following format:

NN MM

u1u_1 v1v_1

u2u_2 v2v_2

\vdots

uMu_M vMv_M

SS

Output

Print a good path with respect to SS of length at most 4N4N in the following format. Specifically, the first line should contain the length KK of the path, and the second line should contain the elements of the path, with spaces in between.

KK

A1A_1 A2A_2 \ldots AKA_K

Sample Input 1

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

Sample Output 1

9
2 5 6 5 6 3 1 3 6

The path (2,5,6,5,6,3,1,3,6)(2, 5, 6, 5, 6, 3, 1, 3, 6) has a length no greater than 4N4N, and

  • it has odd number (11) of 11
  • it has odd number (11) of 22
  • it has even number (22) of 33
  • it has even number (00) of 44
  • it has even number (22) of 55
  • it has odd number (33) of 66

so it is a good path with respect to S=110001S = 110001.

Sample Input 2

3 3
3 1
3 2
1 2
000

Sample Output 2

0

An empty path ()() is a good path with respect to S=000000S = 000000. Alternatively, paths like (1,2,3,1,2,3)(1, 2, 3, 1, 2, 3) are also accepted.

update @ 2024/3/10 10:30:40