Existen dos reinos, $A$ (con $N_1$ ciudades) y $B$ (con $N_2$ ciudades), y $M$ carreteras bidireccionales, cada una conectando una ciudad de $A$ con una ciudad de $B$, de tal manera que no hay más de una carretera conectando cualquier par de ciudades.

Las ciudades en el reino $A$ están numeradas del $1$ al $N_1$, y las ciudades en el reino $B$ están numeradas del $N_1 + 1$ al $N_1 + N_2$. Las carreteras están numeradas del $1$ al $M$; la carretera $i$ conecta dos ciudades $a_i$ y $b_i$, donde $a_i$ y $b_i$ satisfacen $1 \le a_i \le N_1$ y $N_1 + 1 \le b_i \le N_1 + N_2$.

Érase una vez, un virus peligroso apareció en un reino, por lo que los Reyes decidieron cerrar algunas carreteras. Sea $D_j$ el número inicial de carreteras que conectan la ciudad $j$ con otras ciudades, y $d_j$ el número de carreteras actualmente activas (no cerradas) que conectan la ciudad $j$ con otras ciudades.

La carretera $x$ puede cerrarse si y solo si se cumplen las siguientes condiciones antes de cerrar la carretera:

• No fue cerrada anteriormente.
• Los números $d_{a_x}$ y $D_{b_x}$ deben tener la misma paridad (ambos pares o ambos impares).
• Los números $d_{b_x}$ y $D_{a_x}$ deben tener la misma paridad (ambos pares o ambos impares).

Encuentre el número máximo de carreteras que pueden cerrarse y, a continuación, encuentre una secuencia de operaciones de cierre de carreteras tal que se alcance este máximo.

Entrada

La primera línea de la entrada contiene tres enteros, $N_1$, $N_2$ y $M$: el número de ciudades en el reino $A$, el número de ciudades en el reino $B$ y el número de carreteras, respectivamente ($1 \le N_1, N_2, M \le 3000$, $1 \le M \le N_1 \cdot N_2$).

Las siguientes $M$ líneas describen la carretera $i$ y contienen dos enteros $a_i$ y $b_i$ ($1 \le a_i \le N_1$, $N_1 + 1 \le b_i \le N_1 + N_2$): los números de las ciudades conectadas por esa carretera. Puede asumir que, para diferentes $i$ y $j$, $a_i \neq a_j$ o $b_i \neq b_j$.

Salida

En la primera línea, imprima el entero $K$: el número máximo de carreteras que pueden cerrarse. En la segunda línea, imprima $K$ enteros $r_i$ ($1 \le r_i \le M$): los números de las carreteras a cerrar, en el orden en que se cierran.

Si existen varias respuestas óptimas, imprima cualquiera de ellas.

Ejemplos

Entrada 1

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

Salida 1

3
1 4 2

Entrada 2

1 2 2
1 2
1 3

Salida 2

0

Entrada 3

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

Salida 3

5
1 7 6 2 4

Nota

En el primer ejemplo, $D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2$. Inicialmente, $d_1 = 3, d_2 = 2, d_3 = 1, d_4 = 2, d_5 = 2$, por lo que podemos cerrar las siguientes carreteras:

• Carretera 1 que conecta la ciudad 1 y la ciudad 3.
• Carretera 4 que conecta la ciudad 2 y la ciudad 4.
• Carretera 5 que conecta la ciudad 2 y la ciudad 5.

Cerremos la carretera 1, entonces $d_1 = 2, d_2 = 2, d_3 = 0, d_4 = 2, d_5 = 2$. Después de eso, las carreteras que pueden cerrarse son las siguientes:

• Carretera 4 que conecta la ciudad 2 y la ciudad 4.
• Carretera 5 que conecta la ciudad 2 y la ciudad 5.

Cerremos la carretera 4, entonces $d_1 = 2, d_2 = 1, d_3 = 0, d_4 = 1, d_5 = 2$. Ahora, solo podemos cerrar la carretera 2, que conecta la ciudad 1 y la ciudad 4. Después de eso, $d_1 = 1, d_2 = 1, d_3 = 0, d_4 = 0, d_5 = 2$. Se puede demostrar que es imposible cerrar más de tres carreteras, por lo que la respuesta es 3.