도미노 덮기

$N$개의 행과 $M$개의 열로 이루어진 판이 있고, 각 칸에는 번호가 매겨져 있다. 왼쪽에서 $i$번째 열, 위에서 $j$번째 행에 있는 칸의 번호는 $(j-1)\times M + i$이다. 따라서 칸의 번호는 $1$부터 $N\times M$까지이다.

판의 일부 칸 경계에는 선이 그어져 있다. 각 선은 변을 맞대고 인접한 두 칸 사이의 경계에 놓인다.

이 판 전체를 $1\times 2$ 또는 $2\times 1$ 크기의 도미노로 겹치거나 빈칸이 남지 않도록 덮으려고 한다. 하나의 도미노는 변을 맞대고 인접한 두 칸을 덮는다. 단, 두 칸 사이에 선이 그어져 있으면 그 두 칸을 한 도미노로 함께 덮을 수 없고, 선이 없으면 함께 덮을 수 있다. 모든 칸은 정확히 하나의 도미노에만 속해야 한다.

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다 ($1 \le N, M \le 100$). $N$과 $M$ 중 적어도 하나는 짝수이다. 둘째 줄에 선의 개수 $L$이 주어진다 ($0 \le L \le 5\,000$). 이어지는 $L$개의 줄에는 각 선이 나누는, 서로 인접한 두 칸의 번호가 공백으로 구분되어 주어진다. 모든 칸의 번호는 위 규칙에 따라 $1$부터 $N\times M$까지의 정수이다.

판을 규칙에 맞게 도미노로 덮을 수 없으면 첫째 줄에 $-1$을 출력한다. 덮을 수 있으면 다음 규칙으로 유일하게 결정되는 덮기 방법을 출력한다.

어떤 덮기 방법에서 칸 $c$와 같은 도미노로 묶이는 칸의 번호를 $p_c$라 하자. 수열 $(p_1, p_2, \dots, p_{NM})$이 사전순으로 가장 작은 덮기 방법을 선택한다. 즉, 칸 $1$의 짝을 나머지 판도 규칙에 맞게 모두 덮을 수 있다는 조건 아래 될 수 있는 한 작은 번호로 정하고, 이어서 칸 $2$, 칸 $3$, $\dots$ 순서로 같은 방식으로 정한다.

이렇게 정해진 덮기 방법에서 $NM/2$개의 도미노를 출력한다. 각 도미노는 한 줄에, 그 도미노가 덮는 두 칸의 번호를 작은 번호가 앞에 오도록 공백으로 구분하여 출력한다. 줄은 앞에 오는(작은) 번호가 증가하는 순서로 출력한다.