2つの王国 A（$N_1$ 個の都市を持つ）と B（$N_2$ 個の都市を持つ）があり、$M$ 本の双方向道路が存在します。各道路は王国 A の都市と王国 B の都市を接続しており、どの都市のペア間にも道路は最大で1本しか存在しません。

王国 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}$ の偶奇が一致していること（両方とも偶数、または両方とも奇数）。

閉鎖できる道路の最大本数を求め、その最大本数を達成する道路の閉鎖順序を出力してください。

入力

入力の最初の行には、3つの整数 $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$ を表す2つの整数 $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$ となる可能性があることに注意してください。

出力

1行目に、閉鎖できる道路の最大本数 $K$ を出力してください。 2行目に、閉鎖する道路の番号 $r_i$ ($1 \le r_i \le M$) を、閉鎖する順序で $K$ 個出力してください。 最適な答えが複数存在する場合は、そのうちのいずれかを出力してください。

入出力例

入力 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本より多くの道路を閉鎖することは不可能であることが示せるため、答えは 3 です。