Существуют два королевства: $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$-я из этих строк содержит два целых числа $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$: максимальное количество дорог, которые можно закрыть. Во второй строке выведите $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, соединяющая город 1 и город 3. Дорога 4, соединяющая город 2 и город 4. * Дорога 5, соединяющая город 2 и город 5.

Закроем дорогу 1, тогда $d_1 = 2, d_2 = 2, d_3 = 0, d_4 = 2, d_5 = 2$. После этого можно закрыть следующие дороги: Дорога 4, соединяющая город 2 и город 4. Дорога 5, соединяющая город 2 и город 5.

Закроем дорогу 4, тогда $d_1 = 2, d_2 = 1, d_3 = 0, d_4 = 1, d_5 = 2$. Теперь мы можем закрыть только дорогу 2, соединяющую город 1 и город 4. После этого $d_1 = 1, d_2 = 1, d_3 = 0, d_4 = 0, d_5 = 2$. Можно показать, что невозможно закрыть более трех дорог, поэтому ответ — 3.