CF1186F Vus the Cossack and a Graph

哥萨克 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$），表示一条连接顶点 $u_i$ 和 $v_i$ 的边。 保证图中没有自环和重边。 可以证明一定存在满足条件的解。

第一行输出一个整数 $k$（$0 \leq k \leq \lceil \frac{n+m}{2} \rceil$），表示你需要保留的边数。 接下来的 $k$ 行，每行输出两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示你需要保留的边。每条边只能输出一次。

由 ChatGPT 4.1 翻译