두 왕국과 격리

두 왕국 $A$ (도시 $N_1$개)와 $B$ (도시 $N_2$개)가 있고, 양방향 도로가 $M$개 있다. 각 도로는 $A$의 도시 하나와 $B$의 도시 하나를 잇는다. 어떤 두 도시 사이에도 도로는 최대 하나다.

왕국 $A$의 도시는 1번부터 $N_1$번까지, 왕국 $B$의 도시는 $N_1 + 1$번부터 $N_1 + N_2$번까지 번호가 매겨져 있다. 도로는 1번부터 $M$번까지 번호가 매겨져 있으며, 도로 $i$는 도시 $a_i$와 $b_i$를 잇는다. 여기서 $1 \le a_i \le N_1$이고 $N_1 + 1 \le b_i \le N_1 + N_2$이다.

한 왕국에 위험한 바이러스가 나타나서, 왕들은 도로 일부를 닫기로 했다.

$D_j$를 도시 $j$와 다른 도시를 잇는 도로의 처음 개수, $d_j$를 도시 $j$와 다른 도시를 잇는 도로 중 아직 열려 있는(닫히지 않은) 도로의 개수라고 하자.

도로 $x$는 닫기 전에 다음 조건을 모두 만족할 때만 닫을 수 있다.

• 이전에 닫힌 적이 없어야 한다.
• $d_{a_x}$와 $D_{b_x}$의 홀짝이 같아야 한다(둘 다 짝수이거나 둘 다 홀수).
• $d_{b_x}$와 $D_{a_x}$의 홀짝이 같아야 한다(둘 다 짝수이거나 둘 다 홀수).

닫을 수 있는 도로의 최대 개수를 구하고, 그 최대를 달성하는 닫기 순서를 찾아라.

첫 줄에 세 정수 $N_1$, $N_2$, $M$이 주어진다. 각각 왕국 $A$의 도시 수, 왕국 $B$의 도시 수, 도로 수이다($1 \le N_1, N_2, M \le 3000$, $1 \le M \le N_1 \cdot N_2$).

이어서 $M$개의 줄에 도로가 주어진다. $i$번째 줄에는 도로 $i$가 잇는 두 도시 $a_i$와 $b_i$가 주어진다($1 \le a_i \le N_1$, $N_1 + 1 \le b_i \le N_1 + N_2$). $i \ne j$이면 $a_i \ne a_j$ 또는 $b_i \ne b_j$이다.

첫 줄에 닫을 수 있는 도로의 최대 개수 $K$를 출력한다. 둘째 줄에는 닫는 순서대로 도로 번호 $r_i$ ($1 \le r_i \le M$) $K$개를 출력한다.

최적해가 여러 개라면 그중 아무거나 출력해도 된다.

첫 번째 예제에서 $D_1 = 3$, $D_2 = 2$, $D_3 = 1$, $D_4 = 2$, $D_5 = 2$이다. 처음에는 $d$와 $D$가 같으므로 도로 1, 4, 5를 닫을 수 있다.

도로 1을 닫으면 $d_1 = 2$, $d_3 = 0$이 된다. 도로 4와 5는 여전히 닫을 수 있다. 도로 4를 닫으면 $d_2 = 1$, $d_4 = 1$이 되어, 다음에 닫을 수 있는 도로는 도로 2뿐이다. 도로 2를 닫으면 $d_1 = 1$, $d_2 = 1$, $d_3 = 0$, $d_4 = 0$, $d_5 = 2$가 된다. 세 개보다 많이 닫을 수는 없다.