두 개의 왕국 $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$와 $j$에 대해 $a_i = a_j$이거나 $b_i = b_j$일 수 있음을 가정해도 좋습니다.

출력

첫 번째 줄에 폐쇄할 수 있는 도로의 최대 개수인 정수 $K$를 출력합니다. 두 번째 줄에는 폐쇄할 도로의 번호 $r_i$ ($1 \le r_i \le M$) $K$개를 폐쇄하는 순서대로 출력합니다.

여러 개의 최적해가 존재할 경우, 그중 아무거나 출력해도 됩니다.

예제

예제 1

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

3
1 4 2

예제 2

1 2 2
1 2
1 3

0

예제 3

4 3 7
1 5
2 5
2 6
2 7
3 6
4 5
4 7

5
1 7 6 2 4

참고

첫 번째 예제에서 $D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2$입니다. 초기에 $d_1 = 3, d_2 = 2, d_3 = 1, d_4 = 2, d_5 = 2$이므로, 다음 도로들을 폐쇄할 수 있습니다.

• 도시 1과 도시 3을 연결하는 도로 1.
• 도시 2와 도시 4을 연결하는 도로 4.
• 도시 2와 도시 5을 연결하는 도로 5.

도로 1을 폐쇄하면, $d_1 = 2, d_2 = 2, d_3 = 0, d_4 = 2, d_5 = 2$가 됩니다. 그 후, 폐쇄 가능한 도로는 다음과 같습니다.

• 도시 2와 도시 4를 연결하는 도로 4.
• 도시 2와 도시 5를 연결하는 도로 5.

도로 4를 폐쇄하면, $d_1 = 2, d_2 = 1, d_3 = 0, d_4 = 1, d_5 = 2$가 됩니다. 이제 도시 1과 도시 4를 연결하는 도로 2만 폐쇄할 수 있습니다. 그 후, $d_1 = 1, d_2 = 1, d_3 = 0, d_4 = 0, d_5 = 2$가 됩니다. 3개보다 많은 도로를 폐쇄하는 것은 불가능함을 보일 수 있으므로, 정답은 3입니다.