有两个王国 $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

样例输出 1

3
1 4 2

样例输入 2

1 2 2
1 2
1 3

样例输出 2

0

样例输入 3

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

样例输出 3

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。