Domino Tiling

There is a board with $N$ rows and $M$ columns, and every cell is numbered. The cell in the $i$-th column from the left and the $j$-th row from the top has number $(j-1)\times M + i$. Thus the cell numbers run from $1$ to $N\times M$.

Lines are drawn on some of the borders between cells. Each line lies on the border between two edge-adjacent cells.

You want to cover the entire board with $1\times 2$ or $2\times 1$ dominoes so that there is no overlap and no empty cell. A single domino covers two edge-adjacent cells. However, if a line is drawn between two cells they cannot be covered by the same domino; if there is no line between them they may be covered together. Every cell must belong to exactly one domino.

The first line contains two integers $N$ and $M$ separated by a space ($1 \le N, M \le 100$). At least one of $N$ and $M$ is even. The second line contains the number of lines $L$ ($0 \le L \le 5\,000$). Each of the following $L$ lines contains, separated by a space, the numbers of the two edge-adjacent cells that this line divides. All cell numbers are integers from $1$ to $N\times M$ as defined above.

If the board cannot be covered by dominoes under these rules, print $-1$ on the first line. Otherwise print the covering uniquely determined as follows.

For a covering, let $p_c$ be the number of the cell paired with cell $c$ in the same domino. Choose the covering whose sequence $(p_1, p_2, \dots, p_{NM})$ is lexicographically smallest. That is, give cell $1$ the smallest-numbered partner such that the rest of the board can still be fully covered under the rules, then do the same for cell $2$, cell $3$, and so on.

For this covering, print the $NM/2$ dominoes. Print each domino on its own line as the numbers of the two cells it covers, with the smaller number first, separated by a space. Order the lines by increasing smaller number.