Vus the Cossack and a Graph

题意翻译

给定$n$个节点，$m$条边的无向图，记$d_i$为第$i$个点的度。 一个点的度是这个点上连的边数。 Vus 需要保留不超过$\lceil\frac{n+m}{2}\rceil$条边，并保证对于任意一个点$i$满足$f_i \geq \lceil \frac{d_i}{2}\rceil$其中$f_i$表示$i$点在保留的图中的度。 求Vus需要保留哪些边。

题目描述

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!

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

5
2 1
3 2
5 3
5 4
6 5

输入样例 #2

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

输出样例 #2

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

题意翻译

给定$n$个节点，$m$条边的无向图，记$d_i$为第$i$个点的度。 一个点的度是这个点上连的边数。 Vus 需要保留不超过$\lceil\frac{n+m}{2}\rceil$条边，并保证对于任意一个点$i$满足$f_i \geq \lceil \frac{d_i}{2}\rceil$其中$f_i$表示$i$点在保留的图中的度。 求Vus需要保留哪些边。