Có hai vương quốc $A$ (với $N_1$ thành phố) và $B$ (với $N_2$ thành phố), cùng $M$ con đường hai chiều, mỗi con đường nối một thành phố từ $A$ với một thành phố từ $B$, sao cho không có quá một con đường nối giữa bất kỳ cặp thành phố nào.

Các thành phố trong vương quốc $A$ được đánh số từ $1$ đến $N_1$, và các thành phố trong vương quốc $B$ được đánh số từ $N_1 + 1$ đến $N_1 + N_2$. Các con đường được đánh số từ $1$ đến $M$; con đường $i$ nối hai thành phố $a_i$ và $b_i$, trong đó $a_i$ và $b_i$ thỏa mãn $1 \le a_i \le N_1$ và $N_1 + 1 \le b_i \le N_1 + N_2$.

Ngày xửa ngày xưa, một loại virus nguy hiểm xuất hiện ở một vương quốc, vì vậy các vị vua quyết định đóng cửa một số con đường. Gọi $D_j$ là số lượng con đường ban đầu nối thành phố $j$ với các thành phố khác, và $d_j$ là số lượng con đường hiện đang hoạt động (chưa đóng) nối thành phố $j$ với các thành phố khác.

Con đường $x$ có thể được đóng lại nếu và chỉ nếu các điều kiện sau được thỏa mãn trước khi đóng con đường đó:

• Nó chưa từng bị đóng trước đó.
• Các số $d_{a_x}$ và $D_{b_x}$ phải có cùng tính chẵn lẻ (cùng chẵn hoặc cùng lẻ).
• Các số $d_{b_x}$ và $D_{a_x}$ phải có cùng tính chẵn lẻ (cùng chẵn hoặc cùng lẻ).

Hãy tìm số lượng con đường tối đa có thể đóng, và sau đó tìm một trình tự các thao tác đóng đường sao cho đạt được số lượng tối đa này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $N_1, N_2$ và $M$: số lượng thành phố ở vương quốc $A$, số lượng thành phố ở vương quốc $B$, và số lượng con đường ($1 \le N_1, N_2, M \le 3000$, $1 \le M \le N_1 \cdot N_2$).

$M$ dòng tiếp theo, mỗi dòng mô tả con đường $i$ và chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i \le N_1$, $N_1 + 1 \le b_i \le N_1 + N_2$): số hiệu của các thành phố được nối bởi con đường đó. Bạn có thể giả định rằng, với các $i$ và $j$ khác nhau, $a_i \neq a_j$ hoặc $b_i \neq b_j$.

Dữ liệu ra

Trên dòng đầu tiên, in ra số nguyên $K$: số lượng con đường tối đa có thể đóng. Trên dòng thứ hai, in ra $K$ số nguyên $r_i$ ($1 \le r_i \le M$): số hiệu của các con đường cần đóng, theo thứ tự đóng chúng.

Nếu có nhiều phương án tối ưu, hãy in ra bất kỳ phương án nào.

Ví dụ

Ví dụ 1

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

3
1 4 2

Ví dụ 2

1 2 2
1 2
1 3

0

Ví dụ 3

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

5
1 7 6 2 4

Ghi chú

Trong ví dụ đầu tiên, $D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2$. Ban đầu, $d_1 = 3, d_2 = 2, d_3 = 1, d_4 = 2, d_5 = 2$, vì vậy chúng ta có thể đóng các con đường sau:

• Con đường 1 nối thành phố 1 và thành phố 3.
• Con đường 4 nối thành phố 2 và thành phố 4.
• Con đường 5 nối thành phố 2 và thành phố 5.

Giả sử chúng ta đóng con đường 1, khi đó: $d_1 = 2, d_2 = 2, d_3 = 0, d_4 = 2, d_5 = 2$. Sau đó, các con đường có thể đóng là:

• Con đường 4 nối thành phố 2 và thành phố 4.
• Con đường 5 nối thành phố 2 và thành phố 5.

Giả sử chúng ta đóng con đường 4, khi đó: $d_1 = 2, d_2 = 1, d_3 = 0, d_4 = 1, d_5 = 2$. Bây giờ, chúng ta chỉ có thể đóng con đường 2, nối thành phố 1 và thành phố 4. Sau đó, $d_1 = 1, d_2 = 1, d_3 = 0, d_4 = 0, d_5 = 2$. Có thể chứng minh rằng không thể đóng nhiều hơn ba con đường, vì vậy đáp án là 3.