23113번 - Kingdoms and Quarantine 스페셜 저지다국어

문제

There are two kingdoms $A$ (with $N_1$ cities) and $B$ (with $N_2$ cities), and $M$ bidirectional roads, each connecting a city from $A$ and a city from $B,ドル such that there is no more than one road connecting any pair of cities.

The cities in the kingdom $A$ are enumerated from 1ドル$ to $N_1,ドル and the cities in the kingdom $B$ are enumerated from $N_1 + 1$ to $N_1 + N_2$. The roads are enumerated from 1ドル$ to $M$; the road $i$ connects two cities $a_i$ and $b_i,ドル where $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$.

Once upon a time, 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 the city $j$ with other cities, and $d_j$ be the number of currently active (not closed) roads connecting the city $j$ with other cities.

The road $x$ can be closed if and only if following conditions are met before closing the road:

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

Find the maximum number of roads that can be closed, and then find a sequence of road closing operations such that this maximum is achieved.

입력

The first line of input 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, respectively (1ドル \le N_1, N_2, M \le 3000,ドル 1ドル \le M \le N_1 \cdot N_2$).

The $i$-th of the following $M$ lines describes the road $i$ and contains two integers $a_i$ and $b_i$ (1ドル \le a_i \le N_1,ドル $N_1 + 1 \le b_i \le N_1 + N_2$): the numbers of cities connected by that road. You may assume that, for different $i$ and $j,ドル $a_i \ne a_j$ or $b_i \ne b_j$.

출력

On the first line, print the integer $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 roads to be closed, in the order of closing them.

If there are several optimal answers, print any one of them.

제한

힌트

In the first example, $D_1 = 3,ドル $D_2 = 2,ドル $D_3 = 1,ドル $D_4 = 2,ドル $D_5 = 2$.

Initially, $d_1 = 3,ドル $d_2 = 2,ドル $d_3 = 1,ドル $d_4 = 2,ドル $d_5 = 2,ドル so we can close the following roads:

• Road 1 connecting city 1 and city 3.
• Road 4 connecting city 2 and city 4.
• Road 5 connecting city 2 and city 5.

Let us close road 1, then

$d_1 = 2,ドル $d_2 = 2,ドル $d_3 = 0,ドル $d_4 = 2,ドル $d_5 = 2$.

After that, the roads that can be closed are the following:

• Road 4 connecting city 2 and city 4.
• Road 5 connecting city 2 and city 5.

Let us close road 4, then

$d_1 = 2,ドル $d_2 = 1,ドル $d_3 = 0,ドル $d_4 = 1,ドル $d_5 = 2$.

Now, we can close only road 2, connecting city 1 and city 4.

After that, $d_1 = 1,ドル $d_2 = 1,ドル $d_3 = 0,ドル $d_4 = 0,ドル $d_5 = 2$.

It can be shown that it is impossible to close more than three roads, so the answer is 3ドル$.