← 返回题目列表

AtCoder · kupc2020_k

K. 删除边线

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

配点 : 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