시간 제한메모리 제한제출정답맞은 사람정답 비율
8 초 512 MB0000.000%

문제

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.

예제 입력 1

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

예제 출력 1

3
1 4 2

예제 입력 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

힌트

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$.