配点 : 400 点
問題文
N_1 + N_2 頂点 M 边组成单纯无向 2 子图。
该图的顶点编号至 1 减去 N_1 + N_2 ,边连接 1 减去 M 。
辺 i 是顶点 是 a_i 与边缘 b_i 。
这里 a_i, b_i 是 可以表示为1 \le a_i \le N_1 和 N_1 + 1 \le b_i \le N_1 + N_2 满足。
M 在存在所有边的状态下,顶点 i 的顺序是 C_i 对于
你打算尽可能多次执行以下操作。
操作
- 頂点 i 当前的度数为 D_i 。
- 从未删除的边中 1 个选择并删除。
- 但是,选择边的编号为 x 时,必须满足以下所有条件。
- D_{a_x} 该值应乘以 2 的余数为 C_{b_x} 该值应乘以 2 必须与除以后的余数一致。
- D_{b_x} 该值应乘以 2 的余数为 C_{a_x} 该值应乘以 2 必须与除以后的余数一致。
求可进行操作的最大次数,并且求出实现该次数的操作序列 1 个。
制約
- 1 \le N_1 \le 3000
- 1 \le N_2 \le 3000
- 1 \le M \le \min(3000, N_1 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)
入力
输入是按以下格式从标准输入给出的。
N_1 N_2 M a_1 b_1 a_2 b_2 \vdots a_M b_M
出力
求可进行操作的最大次数及完成该次数的操作序列 1 个,并以以下形式输出。
1 行显示可进行操作的最大次数 K 。
i + 1 行目 (1 \le i \le K) 有i 第几次操作选取的边的编号 x_i 。
使操作次数最大化的操作序列可能有多个,但输出其中任意一个都是正确答案。
K x_1 x_2 \ldots x_K
入力例1
2 3 5 1 3 1 4 1 5 2 4 2 5
出力例1
3 1 4 2
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 次以上的操作无法进行。
因此,所求答案是 3 。
入力例2
1 2 2 1 2 1 3
出力例2
0
没有可以选择的边。
入力例3
4 3 7 1 5 2 5 2 6 2 7 3 6 4 5 4 7
出力例3
5 1 7 6 2 4