给你一个无向连通图,由 $$$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