← 返回题目列表

Codeforces · 1494/F

F. 删除边缘

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

给你一个无向连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。您的目标是销毁给定图的所有边。

您可以选择任何顶点作为起始顶点,并从该顶点开始沿着边缘行走。当你沿着边缘行走时,你就摧毁了它。显然,如果边缘被破坏,你就无法沿着它行走。

行走过程中最多可以执行一次模式转换操作,并且只有在某个顶点时才能执行此操作(在穿越边时不能执行此操作)。模式转换后,您经过的边将按以下方式删除:模式转换后的第一条边不被破坏,第二条被破坏,第三条不被破坏,第四条被破坏,依此类推。您无法切换回原来的模式,如果您不想,也可以不执行此操作。

你能摧毁给定图的所有边吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 3000$$$; $$$n - 1 \le m \le \min(\frac{n(n-1)}{2}, 3000$$$)) — 图中的顶点数和边数。

接下来是 $$$m$$$ 行,每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — 第 $$$i$$$ 条边的端点。

这些边形成一个没有多条边的连通无向图。

输出

如果不可能破坏所有边缘,则打印 0。

否则,打印您的操作顺序,如下所示。首先,打印 $$$k$$$ — 操作数 ($$$k \le 2m + 2$$$)。然后,打印序列本身,由 $$$k$$$ 整数组成。第一个整数应该是起始顶点的索引。然后,接下来的每个整数应该是遍历中下一个顶点的索引,或者如果使用模式转换,则为 $$$-1$$$。您最多可以使用一次模式切换。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3 3
1 2
2 3
3 1

输出 #1

4
1 2 3 1

输入 #2

4 3
1 2
2 3
4 2

输出 #2

8
2 -1 1 2 3 2 4 2

输入 #3

5 5
1 2
2 3
3 1
2 4
2 5

输出 #3

9
2 3 1 2 -1 4 2 5 2

输入#4

5 5
1 2
2 3
3 1
2 4
4 5

输出#4

8
5 4 2 3 1 -1 2 1

输入 #5

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

输出 #5

0