#abc244g. G - Construct Good Path
G - Construct Good Path
Score : points
问题描述
给定一个包含 个顶点和 条边的简单连通无向图。(如果图中没有重边且没有自环,则称该图为简单图。) 对于 ,第 条边连接顶点 和顶点 。
若满足以下两个条件,则称序列 是一条长度为 的 路径:
- 对于所有 ,有 。
- 对于所有 ,顶点 和顶点 直接通过一条边相连。
空序列被视为长度为 的路径。
给定一个由 和 组成的长度为 的字符串 。若满足以下条件,则称路径 对于 是一条 好路径:
- 对于所有 ,满足:
- 若 ,则 中包含偶数个 ;
- 若 ,则 中包含奇数个 。
根据本题的约束条件,可以证明存在至少一条长度不超过 的对于 的好路径。请打印出一条长度不超过 的对于 的好路径。
以上为通义千问 qwen-max 翻译,仅供参考。
Problem Statement
You are given a simple connected undirected graph with vertices and edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For , the -th edge connects Vertex and Vertex .
A sequence is said to be a path of length if both of the following two conditions are satisfied:
- For all , it holds that .
- For all , Vertex and Vertex are directly connected with an edge.
An empty sequence is regarded as a path of length .
You are given a sting of length consisting of and . A path is said to be a good path with respect to if the following conditions are satisfied:
- For all , it holds that:
- if , then has even number of 's.
- if , then has odd number of 's.
Under the Constraints of this problem, it can be proved that there is at least one good path with respect to of length at most . Print a good path with respect to of length at most .
Constraints
- $N-1 \leq M \leq \min\lbrace 2 \times 10^5, \frac{N(N-1)}{2}\rbrace$
- The given graph is simple and connected.
- , and are integers.
- is a string of length consisting of and .
Input
Input is given from Standard Input in the following format:
Output
Print a good path with respect to of length at most in the following format. Specifically, the first line should contain the length of the path, and the second line should contain the elements of the path, with spaces in between.
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 has a length no greater than , and
- it has odd number () of
- it has odd number () of
- it has even number () of
- it has even number () of
- it has even number () of
- it has odd number () of
so it is a good path with respect to .
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 . Alternatively, paths like are also accepted.
update @ 2024/3/10 10:30:40