|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|8 초||512 MB||0||0||0||0.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:
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.
2 3 5 1 3 1 4 1 5 2 4 2 5
3 1 4 2
1 2 2 1 2 1 3
4 3 7 1 5 2 5 2 6 2 7 3 6 4 5 4 7
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:
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:
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$.