Vus the Cossack and a Graph
Contest: Codeforces Round 571 (Div. 2)
Difficulty rating: 2400
Tags: dfs and similar, graphs, greedy, implementation

Vus the Cossack has a simple graph with $$$n$$$ vertices and $$$m$$$ edges. Let $$$d_i$$$ be a degree of the $$$i$$$-th vertex. Recall that a degree of the $$$i$$$-th vertex is the number of conected edges to the $$$i$$$-th vertex.

He needs to remain not more than $$$\lceil \frac{n+m}{2} \rceil$$$ edges. Let $$$f_i$$$ be the degree of the $$$i$$$-th vertex after removing. He needs to delete them in such way so that $$$\lceil \frac{d_i}{2} \rceil \leq f_i$$$ for each $$$i$$$. In other words, the degree of each vertex should not be reduced more than twice.

Help Vus to remain the needed edges!

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^6$$$, $$$0 \leq m \leq 10^6$$$) — the number of vertices and edges respectively.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — vertices between which there is an edge.

It is guaranteed that the graph does not have loops and multiple edges.

It is possible to show that the answer always exists.

Output format:
In the first line, print one integer $$$k$$$ ($$$0 \leq k \leq \lceil \frac{n+m}{2} \rceil$$$) — the number of edges which you need to remain.

In each of the next $$$k$$$ lines, print two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — the vertices, the edge between which, you need to remain. You can not print the same edge more than once.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
6 6
1 2
2 3
3 4
4 5
5 3
6 5

Example output:
5
2 1
3 2
5 3
5 4
6 5

Example input:
10 20
4 3
6 5
4 5
10 8
4 8
5 8
10 4
9 5
5 1
3 8
1 2
4 7
1 4
10 7
1 7
6 1
9 6
3 9
7 9
6 2

Example output:
12
2 1
4 1
5 4
6 5
7 1
7 4
8 3
8 5
9 3
9 6
10 4
10 7

Editorial:
At first, let's create a fictive vertex (I'll call it $$$0$$$ vertex) and connect it with all of the vertices which have odd degree. Now all the vertices including $$$0$$$ vertex have even degree. The statement that $$$0$$$ vertex will have even degree too can be easily proven using the fact that the sum of degrees of all vertices equals to the number of edges multiplied by two. Let's denote the number of edges in the new graph as $$$k$$$.
There were $$$m$$$ edges initially and we added at most $$$n$$$ new edges that connect fictive vertex with the real ones, so it always holds that $$$k \le n + m$$$.
Now, since all the vertices have even degree we can find Euler cycle of the new graph. Let's define $$$e_1, e_2, \ldots, e_k$$$ as an array of all edges of the graph, ordered as in found Euler cycle. Now we can iterate over the array $$$e$$$ and delete all the edges on even positions. Due to this action now the new graph contains at most $$$\lceil \frac{k}{2} \rceil \le \lceil \frac{n+m}{2} \rceil$$$ edges. That is exactly what we needed!
It is interesting that in the new graph by deleting the edges the way mentioned above, the degree of each vertex would not be reduced more than twice. How to prove that? Well, you can think about it the following way:
Let's say that the $$$e_i$$$ edge connects some vertices $$$a$$$ and $$$b$$$, that means that the $$$e_{i+1}$$$ edge connects vertex $$$b$$$ with some vertex $$$c$$$. If $$$i$$$ is odd, then we will delete only the $$$e_{i+1}$$$ edge, and if $$$i$$$ is even, then we will delete only the $$$e_i$$$ edge. And that happens for every vertex: if some edge $$$i$$$ enters it, then we will either delete $$$i$$$-th edge or $$$i+1$$$-th edge. So at most half of edges connected to a vertex will be deleted. If the length of Euler cycle is odd, then the last edge in it won't be deleted at all, so the algorithm will still work correctly.
But that works for the new graph, which contains fictive vertex. But we need to solve the problem for the real graph. We can not simply delete all the edges from the real graph, that were on even positions in Euler cycle mentioned above. Here is the examle where it does not work (numbers near the edges show their positions in $$$e$$$ array, edges that would need to be removed are highlited with red):
If we removed edge between vertices $$$2$$$ and $$$3$$$, degree of vertex $$$3$$$ would become $$$0$$$ which is definetely less then $$$\lceil \frac{d_3}{2} \rceil = 1$$$. How do we avoid this bad situation? We can simply do the following:
• If $$$e_i$$$ is a fictive edge (i.e. it connects a real vertex with fictive one), then we do not really care about it, since we have to output answer about the real graph.
• If $$$e_i$$$ is a real edge (i.e it connects only real vertices) and we have to delete it, then we should look if $$$e_{i-1}$$$ or $$$e_{i+1}$$$ is a ficive edge. If either of them is one, then we can delete the fictive edge instead of the real edge $$$e_i$$$ (i.e. we simply do not delete $$$e_i$$$ from the graph), otherwise we delete the edge. (Note that if $$$e_i$$$ is the last edge in the Euler cycle, then instead of checking the $$$e_{k+1}$$$ edge which does not exist, you check if $$$e_1$$$ is fictive or not, similar goes for the case if $$$i = 1$$$).
It is obvious that by doing so we do not change the number of edges deleted. It is also easy to see that the degree of a $$$i-th$$$ vertex in the new graph is at most $$$d_i + 1$$$. We still delete at most $$$\lfloor \frac{d_i + 1}{2} \rfloor$$$ edges connected to it (or $$$\lfloor \frac{d_i}{2} \rfloor$$$ if it initially had an even degree), but in case when it's degree was "artificially" increased, we prefer to delete the fictive edge, which we do not care about. The last question is: whether there we will a fictive edge which we will try to delete more than once? It is easy to prove that there is no such edge, you can try it by yourself.
That's it, the problem is solved.
Note that the graph is not necessarily connected, so you should find Euler cycle and do the following steps for each component independently.
In order to better understand the solution, check out author's source code: