AT_kupc2020_k Deleting Edges

有一个简单无向二分图，包含 $N_1 + N_2$ 个顶点和 $M$ 条边。 图中的顶点从 $1$ 编号到 $N_1 + N_2$，边从 $1$ 编号到 $M$。 第 $i$ 条边连接了顶点 $a_i$ 和顶点 $b_i$。 其中，$a_i$ 满足 $1 \le a_i \le N_1$，$b_i$ 满足 $N_1 + 1 \le b_i \le N_1 + N_2$。 在所有 $M$ 条边初始存在时，顶点 $i$ 的度数记为 $C_i$。 你的任务是尽可能多地执行以下操作。

输入通过标准输入给出，格式如下： > $N_1$ $N_2$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\cdots$ $a_M$ $b_M$

输出可以执行的最大操作次数和一个操作序列。具体内容包括： - 第一行输出最大操作次数 $K$。 - 接下来的 $K$ 行中，每行输出一个操作中选择的边的编号 $x_i$。 如果能达到最大操作次数的序列有多种，输出其中任意一种即可。 格式如下： > $K$ $x_1$ $x_2$ $\ldots$ $x_K$

### 操作规则 - 当前顶点 $i$ 的度数为 $D_i$。 - 选择一条尚未删除的边进行删除。 - 选定的边编号为 $x$ 时，必须满足： - $D_{a_x}$ 除以 $2$ 的余数与 $C_{b_x}$ 除以 $2$ 的余数不同。 - $D_{b_x}$ 除以 $2$ 的余数与 $C_{a_x}$ 除以 $2$ 的余数不同。 计算可以执行的最大操作次数，并给出一种达到最大数量的操作序列。 ### 约束条件 - $1 \le N_1 \le 3000$ - $1 \le N_2 \le 3000$ - $1 \le M \le \min(3000, N_1 \times N_2)$ - $1 \le a_i \le N_1\ (1 \le i \le M)$ - $N_1 + 1 \le b_i \le N_1 + N_2\ (1 \le i \le M)$ - 对于 $1 \le i < j \le M$，$(a_i, b_i) \neq (a_j, b_j)$ ### 样例解释 1 在初始状态下，顶点度数为 $C_1 = 3, C_2 = 2, C_3 = 1, C_4 = 2, C_5 = 2$，现时 $D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2$。可以删除的边有： - 连接顶点 $1$ 和顶点 $3$ 的边 $1$ - 连接顶点 $2$ 和顶点 $4$ 的边 $4$ - 连接顶点 $2$ 和顶点 $5$ 的边 $5$ 选择删除边 $1$，则 $D_1 = 2, D_2 = 2, D_3 = 0, D_4 = 2, D_5 = 2$，此时可删除： - 连接顶点 $2$ 和顶点 $4$ 的边 $4$ - 连接顶点 $2$ 和顶点 $5$ 的边 $5$ 选择删除边 $4$ 后，$D_1 = 2, D_2 = 1, D_3 = 0, D_4 = 1, D_5 = 2$。接下来可以删除的只有： - 连接顶点 $1$ 和顶点 $4$ 的边 $2$ 删除边 $2$ 后，即无可删除的边，度数为 $D_1 = 1, D_2 = 1, D_3 = 0, D_4 = 0, D_5 = 2$。该示例中执行了 $3$ 次操作，且无法超过这个次数，因此答案是 $3$。 ### 样例解释 2 没有满足条件的边可以选择删除。 **本翻译由 AI 自动生成**