Kingdoms and Quarantine

There are two kingdoms $A$ (with $N_1$ cities) and $B$ (with $N_2$ cities), and $M$ bidirectional roads. Each road connects a city from $A$ and a city from $B$. No pair of cities is connected by more than one road.

The cities in kingdom $A$ are numbered from $1$ to $N_1$. The cities in kingdom $B$ are numbered from $N_1 + 1$ to $N_1 + N_2$. The roads are numbered from $1$ to $M$. Road $i$ connects cities $a_i$ and $b_i$, where $1 \le a_i \le N_1$ and $N_1 + 1 \le b_i \le N_1 + N_2$.

A dangerous virus appeared in one kingdom, so the Kings decided to close some roads.

Let $D_j$ be the initial number of roads connecting city $j$ to other cities, and let $d_j$ be the number of roads connecting city $j$ to other cities that are still active (not closed).

Road $x$ can be closed if and only if the following conditions hold before it is closed:

• It was not closed before.
• $d_{a_x}$ and $D_{b_x}$ have the same parity (both even or both odd).
• $d_{b_x}$ and $D_{a_x}$ have the same parity (both even or both odd).

Find the maximum number of roads that can be closed, and a sequence of closing operations that achieves this maximum.

The first line contains three integers $N_1$, $N_2$, and $M$: the number of cities in kingdom $A$, the number of cities in kingdom $B$, and the number of roads ($1 \le N_1, N_2, M \le 3000$, $1 \le M \le N_1 \cdot N_2$).

The next $M$ lines describe the roads. Line $i$ contains two integers $a_i$ and $b_i$, the cities connected by road $i$ ($1 \le a_i \le N_1$, $N_1 + 1 \le b_i \le N_1 + N_2$). For $i \ne j$, either $a_i \ne a_j$ or $b_i \ne b_j$.

On the first line, print $K$, the maximum number of roads that can be closed. On the second line, print $K$ integers $r_i$ ($1 \le r_i \le M$), the numbers of the roads to close, in the order they are closed.

If several optimal answers exist, print any of them.

In the first sample, $D_1 = 3$, $D_2 = 2$, $D_3 = 1$, $D_4 = 2$, $D_5 = 2$. Initially $d$ equals $D$, so roads 1, 4, and 5 can be closed.

After closing road 1, $d_1 = 2$ and $d_3 = 0$. Roads 4 and 5 can still be closed. After closing road 4, $d_2 = 1$ and $d_4 = 1$, so only road 2 can be closed next. After closing road 2, $d_1 = 1$, $d_2 = 1$, $d_3 = 0$, $d_4 = 0$, and $d_5 = 2$. No more than three roads can be closed.