Delete The Edges
Contest: Educational Codeforces Round 105 (Rated for Div. 2)
Difficulty rating: 2900
Tags: brute force, constructive algorithms, dfs and similar, graphs, implementation

You are given an undirected connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Your goal is to destroy all edges of the given graph.

You may choose any vertex as the starting one and begin walking from it along the edges. When you walk along an edge, you destroy it. Obviously, you cannot walk along an edge if it is destroyed.

You can perform the mode shift operation at most once during your walk, and this operation can only be performed when you are at some vertex (you cannot perform it while traversing an edge). After the mode shift, the edges you go through are deleted in the following way: the first edge after the mode shift is not destroyed, the second one is destroyed, the third one is not destroyed, the fourth one is destroyed, and so on. You cannot switch back to the original mode, and you don't have to perform this operation if you don't want to.

Can you destroy all the edges of the given graph?

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3000$$$; $$$n - 1 \le m \le \min(\frac{n(n-1)}{2}, 3000$$$)) — the numbef of vertices and the number of edges in the graph.

Then $$$m$$$ lines follow, each containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge.

These edges form a connected undirected graph without multiple edges.

Output format:
If it's impossible to destroy all of the edges, print 0.

Otherwise, print the sequence of your actions as follows. First, print $$$k$$$ — the number of actions ($$$k \le 2m + 2$$$). Then, print the sequence itself, consisting of $$$k$$$ integers. The first integer should be the index of the starting vertex. Then, each of the next integers should be either the index of the next vertex in your traversal, or $$$-1$$$ if you use mode shift. You are allowed to use mode shift at most once.

If there are multiple answers, print any of them.

Constraints:
Time limit: 8.0 s
Memory limit: 512.0 MB

Example input:
3 3
1 2
2 3
3 1

Example output:
4
1 2 3 1

Example input:
4 3
1 2
2 3
4 2

Example output:
8
2 -1 1 2 3 2 4 2

Editorial:
Let's suppose our graph is split into two graphs $$$G_1$$$ and $$$G_2$$$, the first graph contains the edges we delete before the mode shift, the second graph contains the edges we delete after the mode shift.
It's quite obvious that the graph $$$G_1$$$ has an eulerian path. The structure of $$$G_2$$$ is a bit harder to analyze, but we can prove that it is always a star graph (a vertex and some other vertices connected directly to it), and the center of the star coincides with the last vertex in the eulerian path in $$$G_1$$$. To prove that $$$G_2$$$ is a star graph, we can consider the second part of the path (after the mode shift) backward: the last edge we traversed was deleted, and the previous-to-last move could have been only along that edge. The third-last and the fourth-last moves should have been along another edge connecting some vertex to the center of the star, and so on.
Okay, how do we find a way to split the graph into $$$G_1$$$ and $$$G_2$$$? Iterate on the center of the star (let it be $$$c$$$). For the graph $$$G_1$$$ to contain an eulerian path, it should have at most $$$2$$$ vertices with an odd degree. Let's construct $$$G_2$$$ in such a way that we minimize the number of odd vertices in $$$G_1$$$ — for each edge incident to $$$c$$$, we either move it to $$$G_1$$$ or $$$G_2$$$ in such a way that the resulting degree of the other vertex is even. All other edges belong to $$$G_1$$$.
If there is an eulerian path in $$$G_1$$$ that ends in $$$c$$$, we are done. Otherwise, we should iterate on some edge adjacent to $$$c$$$ and change its status (in order to check if $$$G_1$$$ can have an eulerian path after that). We can't "flip" two edges because flipping two edges increases the number of odd vertices in $$$G_1$$$ at least by $$$2$$$ (if it is already $$$2$$$ or greater, the eulerian path won't exist, and if it's $$$0$$$, then flipping two edges creates two odd vertices, none of which is $$$c$$$, so eulerian path can't end in $$$c$$$). After flipping each edge, we try to find an eulerian path in $$$G_1$$$ once again and flip the edge back. After checking the vertex $$$c$$$ as the center of the star, we return all adjacent edges to $$$G_1$$$ and move to the next vertex.
The whole algorithm requires checking for the existence of the eulerian path $$$O(n + m)$$$ times, so it should work in $$$O((n+m)^2)$$$ or $$$O((n+m)^2 \log n)$$$ depending on the implementation.
Fun fact: initially I wanted to give a harder version of a problem with $$$n, m \le 2 \cdot 10^5$$$ that would require some sort of dynamic connectivity to check for an eulerian path fast, but when I started coding it, I realized that implementation there was a bit painful, so I've decided to drop the constraints to allow quadratic solutions.