有兩個王國 $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 \neq a_j$ 或 $b_i \neq b_j$。

輸出格式

第一行輸出整數 $K$：最多可以關閉的道路數量。第二行輸出 $K$ 個整數 $r_i$ ($1 \le r_i \le M$)：關閉道路的順序。

若有多組最佳解，輸出其中任意一組即可。

範例

範例 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。