Problem Description

There is a simple undirected bipartite graph consisting of $ N_1 + N_2 $ vertices and $ M $ edges.

The vertices of the graph are numbered from $ 1 $ to $ N_1 + N_2 $, and the edges are numbered from $ 1 $ to $ M $.

Edge $ i $ connects vertex $ a_i $ and vertex $ b_i $.

Here, $ a_i $ and $ b_i $ satisfy $1 \le a_i \le N_1$ and $N_1 + 1 \le b_i \le N_1 + N_2$.

Let $ C_i $ be the degree of vertex $ i $ in the state where all $ M $ edges are present.

You are trying to perform the following operation as many times as possible.

Input Format

The input is given from the standard input in the following format:

$ N_1 $ $ N_2 $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $\vdots$ $ a_M $ $ b_M $

Output Format

Determine the maximum number of operations that can be performed and one sequence of operations that achieves this, and output it in the following format:

The first line should contain the maximum number of operations $ K $.

The $ i + 1 $ line (for $1 \le i \le K$) should contain the edge number $ x_i $ chosen in the $ i $th operation.

There may be multiple sequences of operations that achieve the maximum number of operations, but any one of them will be considered correct.

$ K $ $ x_1 $ $ x_2 $ $\ldots$ $ x_K $

Sample Input and Output

Sample Input #1

2 3 5
1 3
1 4
1 5
2 4
2 5

Sample Output #1

3
1 4 2

Sample Input #2

1 2 2
1 2
1 3

Sample Output #2

0

Sample Input #3

4 3 7
1 5
2 5
2 6
2 7
3 6
4 5
4 7

Sample Output #3

5
1 7 6 2 4

Notes/Hints

Operation

• Let $ D_i $ be the current degree of vertex $ i $.
• Choose one edge that has not been deleted yet.
• However, when the edge number chosen is $ x $, all of the following conditions must be satisfied:
• The remainder of $ D_{a_x} $ divided by $ 2 $ must match the remainder of $ C_{b_x} $ divided by $ 2 $.
• The remainder of $ D_{b_x} $ divided by $ 2 $ must match the remainder of $ C_{a_x} $ divided by $ 2 $.

Determine the maximum number of operations that can be performed and further determine one sequence of operations that achieves this.

Constraints

• $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$ (for $1 \le i \le M$)
• $N_1 + 1 \le b_i \le N_1 + N_2$ (for $1 \le i \le M$)
• For $1 \le i < j \le M$, $(a_i, b_i) \neq (a_j, b_j)$

Sample Explanation 1

$ C_1 = 3, C_2 = 2, C_3 = 1, C_4 = 2, C_5 = 2 $. Currently, $ D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2 $, so the edges that can be deleted by the operation are:
- Edge $ 1 $ connecting vertex $ 1 $ and vertex $ 3 $
- Edge $ 4 $ connecting vertex $ 2 $ and vertex $ 4 $
- Edge $ 5 $ connecting vertex $ 2 $ and vertex $ 5 $

After deleting edge $ 1 $ by the operation, $ D_1 = 2, D_2 = 2, D_3 = 0, D_4 = 2, D_5 = 2 $. Therefore, the edges that can be deleted by the next operation are:
- Edge $ 4 $ connecting vertex $ 2 $ and vertex $ 4 $
- Edge $ 5 $ connecting vertex $ 2 $ and vertex $ 5 $

After deleting edge $ 4 $, $ D_1 = 2, D_2 = 1, D_3 = 0, D_4 = 1, D_5 = 2 $. The only edge that can be deleted next is:
- Edge $ 2 $ connecting vertex $ 1 $ and vertex $ 4 $

After deleting edge $ 2 $, $ D_1 = 1, D_2 = 1, D_3 = 0, D_4 = 0, D_5 = 2 $, and no more edges can be deleted. In the above example, $ 3 $ operations were performed, but no more operations can be performed beyond $ 3 $ times. Therefore, the answer is $ 3 $.

Sample Explanation 2

No edges can be chosen.

见题面 Input 部分

见题面 Output 部分