Il existe deux royaumes $A$ (avec $N_1$ villes) et $B$ (avec $N_2$ villes), ainsi que $M$ routes bidirectionnelles, chacune reliant une ville de $A$ à une ville de $B$, de telle sorte qu'il n'y ait pas plus d'une route reliant une paire de villes donnée.

Les villes du royaume $A$ sont numérotées de $1$ à $N_1$, et les villes du royaume $B$ sont numérotées de $N_1 + 1$ à $N_1 + N_2$. Les routes sont numérotées de $1$ à $M$ ; la route $i$ relie deux villes $a_i$ et $b_i$, où $a_i$ et $b_i$ satisfont $1 \le a_i \le N_1$ et $N_1 + 1 \le b_i \le N_1 + N_2$.

Il était une fois, un virus dangereux apparut dans l'un des royaumes, et les Rois décidèrent de fermer certaines routes. Soit $D_j$ le nombre initial de routes reliant la ville $j$ aux autres villes, et $d_j$ le nombre de routes actuellement actives (non fermées) reliant la ville $j$ aux autres villes.

La route $x$ peut être fermée si et seulement si les conditions suivantes sont remplies avant la fermeture de la route :

• Elle n'a pas été fermée auparavant.
• Les nombres $d_{a_x}$ et $D_{b_x}$ doivent avoir la même parité (tous deux pairs ou tous deux impairs).
• Les nombres $d_{b_x}$ et $D_{a_x}$ doivent avoir la même parité (tous deux pairs ou tous deux impairs).

Trouvez le nombre maximum de routes pouvant être fermées, puis trouvez une séquence d'opérations de fermeture de routes permettant d'atteindre ce maximum.

Entrée

La première ligne de l'entrée contient trois entiers, $N_1$, $N_2$ et $M$ : le nombre de villes dans le royaume $A$, le nombre de villes dans le royaume $B$, et le nombre de routes, respectivement ($1 \le N_1, N_2, M \le 3000$, $1 \le M \le N_1 \cdot N_2$).

Les $M$ lignes suivantes décrivent la route $i$ et contiennent deux entiers $a_i$ et $b_i$ ($1 \le a_i \le N_1$, $N_1 + 1 \le b_i \le N_1 + N_2$) : les numéros des villes reliées par cette route. Vous pouvez supposer que, pour deux routes $i$ et $j$ distinctes, $a_i \neq a_j$ ou $b_i \neq b_j$.

Sortie

Sur la première ligne, affichez l'entier $K$ : le nombre maximum de routes pouvant être fermées. Sur la seconde ligne, affichez $K$ entiers $r_i$ ($1 \le r_i \le M$) : les numéros des routes à fermer, dans l'ordre de leur fermeture.

S'il existe plusieurs réponses optimales, affichez-en une quelconque.

Exemples

Entrée 1

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

Sortie 1

3
1 4 2

Entrée 2

1 2 2
1 2
1 3

Sortie 2

0

Entrée 3

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

Sortie 3

5
1 7 6 2 4

Remarque

Dans le premier exemple, $D_1 = 3, D_2 = 2, D_3 = 1, D_4 = 2, D_5 = 2$. Initialement, $d_1 = 3, d_2 = 2, d_3 = 1, d_4 = 2, d_5 = 2$, nous pouvons donc fermer les routes suivantes :

• Route 1 reliant la ville 1 et la ville 3.
• Route 4 reliant la ville 2 et la ville 4.
• Route 5 reliant la ville 2 et la ville 5.

Fermons la route 1, alors $d_1 = 2, d_2 = 2, d_3 = 0, d_4 = 2, d_5 = 2$. Après cela, les routes qui peuvent être fermées sont les suivantes :

• Route 4 reliant la ville 2 et la ville 4.
• Route 5 reliant la ville 2 et la ville 5.

Fermons la route 4, alors $d_1 = 2, d_2 = 1, d_3 = 0, d_4 = 1, d_5 = 2$. Maintenant, nous ne pouvons fermer que la route 2, reliant la ville 1 et la ville 4. Après cela, $d_1 = 1, d_2 = 1, d_3 = 0, d_4 = 0, d_5 = 2$. Il peut être démontré qu'il est impossible de fermer plus de trois routes, donc la réponse est 3.