問題文

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)

入力例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