Istnieją dwa królestwa: $A$ (z $N_1$ miastami) oraz $B$ (z $N_2$ miastami), a także $M$ dwukierunkowych dróg, z których każda łączy miasto z królestwa $A$ z miastem z królestwa $B$, przy czym żadna para miast nie jest połączona więcej niż jedną drogą.

Miasta w królestwie $A$ są ponumerowane od $1$ do $N_1$, a miasta w królestwie $B$ od $N_1 + 1$ do $N_1 + N_2$. Drogi są ponumerowane od $1$ do $M$; droga $i$ łączy dwa miasta $a_i$ oraz $b_i$, gdzie $1 \le a_i \le N_1$ oraz $N_1 + 1 \le b_i \le N_1 + N_2$.

Pewnego razu w jednym z królestw pojawił się niebezpieczny wirus, więc królowie postanowili zamknąć niektóre drogi. Niech $D_j$ oznacza początkową liczbę dróg łączących miasto $j$ z innymi miastami, a $d_j$ oznacza liczbę aktualnie aktywnych (niezamkniętych) dróg łączących miasto $j$ z innymi miastami.

Drogę $x$ można zamknąć wtedy i tylko wtedy, gdy przed jej zamknięciem spełnione są następujące warunki: Droga nie została wcześniej zamknięta. Liczby $d_{a_x}$ oraz $D_{b_x}$ mają tę samą parzystość (obie są parzyste lub obie są nieparzyste). * Liczby $d_{b_x}$ oraz $D_{a_x}$ mają tę samą parzystość (obie są parzyste lub obie są nieparzyste).

Znajdź maksymalną liczbę dróg, które można zamknąć, a następnie wyznacz sekwencję operacji zamykania dróg, dzięki której osiągnięta zostanie ta maksymalna liczba.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $N_1$, $N_2$ oraz $M$: odpowiednio liczbę miast w królestwie $A$, liczbę miast w królestwie $B$ oraz liczbę dróg ($1 \le N_1, N_2, M \le 3000$, $1 \le M \le N_1 \cdot N_2$).

Każda z kolejnych $M$ linii opisuje drogę $i$ i zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i \le N_1$, $N_1 + 1 \le b_i \le N_1 + N_2$): numery miast połączonych tą drogą. Można założyć, że dla różnych $i$ oraz $j$, $a_i \neq a_j$ lub $b_i \neq b_j$.

Wyjście

W pierwszej linii wypisz liczbę całkowitą $K$: maksymalną liczbę dróg, które można zamknąć. W drugiej linii wypisz $K$ liczb całkowitych $r_i$ ($1 \le r_i \le M$): numery dróg w kolejności ich zamykania.

Jeśli istnieje kilka optymalnych rozwiązań, wypisz dowolne z nich.

Przykład

Przykład 1

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

3
1 4 2

Przykład 2

1 2 2
1 2
1 3

0

Przykład 3

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

5
1 7 6 2 4

Uwagi

W pierwszym przykładzie $D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2$. Początkowo $d_1 = 3, d_2 = 2, d_3 = 1, d_4 = 2, d_5 = 2$, więc możemy zamknąć następujące drogi: Droga 1 łącząca miasto 1 i miasto 3. Droga 4 łącząca miasto 2 i miasto 4. * Droga 5 łącząca miasto 2 i miasto 5.

Zamknijmy drogę 1, wtedy: $d_1 = 2, d_2 = 2, d_3 = 0, d_4 = 2, d_5 = 2$. Po tym fakcie drogi, które można zamknąć, to: Droga 4 łącząca miasto 2 i miasto 4. Droga 5 łącząca miasto 2 i miasto 5.

Zamknijmy drogę 4, wtedy: $d_1 = 2, d_2 = 1, d_3 = 0, d_4 = 1, d_5 = 2$. Teraz możemy zamknąć tylko drogę 2, łączącą miasto 1 i miasto 4. Po tym fakcie $d_1 = 1, d_2 = 1, d_3 = 0, d_4 = 0, d_5 = 2$. Można wykazać, że nie da się zamknąć więcej niż trzech dróg, więc odpowiedzią jest 3.