哥萨克 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