← 返回题目列表

Codeforces · 1186/F

F. 哥萨克 Vus 和图表

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

哥萨克 Vus 有一个简单的图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。令 $$$d_i$$$ 为第 $$$i$$$ 个顶点的度数。回想一下,第$$$i$$$顶点的度数是与第$$$i$$$顶点相连的边的数量。

他需要保留不超过 $$$\lceil \frac{n+m}{2} \rceil$$$ 边。令 $$$f_i$$$ 为移除后第 $$$i$$$ 个顶点的度数。他需要以这样的方式删除它们,以便每个 $$$i$$$ 都有 $$$\lceil \frac{d_i}{2} \rceil \leq f_i$$$。换句话说,每个顶点的度数不应减少超过两倍。

帮助 Vus 保持所需的边缘!

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 10^6$$$, $$$0 \leq m \leq 10^6$$$) - 分别是顶点和边的数量。

接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — 顶点之间有一条边。

保证图没有环和重边。

可以证明答案总是存在。

输出

在第一行中,打印一个整数 $$$k$$$ ($$$0 \leq k \leq \lceil \frac{n+m}{2} \rceil$$$) - 您需要保留的边数。

在接下来的 $$$k$$$ 行中,打印两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) - 顶点,以及它们之间的边,您需要保留。您不能多次打印同一边缘。

示例

输入 #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