시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 50 10 9 30.000%

문제

각 칸에 번호가 붙어 있는 N×M 크기의 체스판이 있다. 이 판에는 몇 개의 선이 그러져 있는데, 각각의 선은 두 개의 서로 다른 칸의 경계에 그려진다. 예를 들어 아래의 체스판은 N=4, M=5이고, 9개의 선이 그려져 있는 모습이다.

이 체스판을 1×2 또는 2×1 크기의 도미노로 모두 덮으려고 한다. 단, 선으로 분리되어 있는 두 칸을 하나의 도미노로 덮을 수는 없다. 예를 들어, 위의 그림에서 1번 칸과 2번 칸은 하나의 도미노로 덮을 수 있지만, 6번 칸과 7번 칸은 하나의 도미노로 덮을 수 없다. 아래는 이와 같은 조건을 만족하면서 체스판을 모두 덮은 예이다.

입력

첫째 줄에 N과 M(1≤N, M≤100)이 빈 칸을 사이에 두고 주어진다. N과 M 중 적어도 하나는 짝수이다. 둘째 줄에는 선의 개수 L(0≤L≤5,000)이 주어진다. 이어서 L개의 줄에 걸쳐 선을 나타내는 두 개의 칸 번호가 빈 칸을 사이에 두고 주어진다. 이는 두 칸을 분리시키는 선이라는 의미이다. 번호는 N×M 이하의 자연수로 왼쪽으로부터 i번째, 위로부터 j번째 칸이 (j-1)×M+i 번이 된다.

출력

첫째 줄부터 N×M÷2개 줄에 도미노를 놓을 두 칸의 번호를 빈 칸을 사이에 두고 출력한다. 1×2 또는 2×1 크기의 도미노를 놓을 두 칸은 반드시 인접해 있어야 하며, 선으로 분리되어 있는 두 칸을 덮어서는 안 된다. 하나의 칸에 여러 개의 도미노를 놓아서도 안 되며, 반드시 모든 칸을 겹치지 않게 덮는 해를 출력해야 한다. 출력하는 순서는 상관이 없으며, 도미노를 놓는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다.

예제 입력

4 5
9
8 7
13 14
14 19
6 7
12 7
4 9
12 13
14 9
9 10

예제 출력

3 4
1 6
2 7
8 9
5 10
14 15
11 16
12 17
13 18
19 20

힌트

출처

Olympiad > International Olympiad in Informatics > IOI 2005 P2번

  • 문제를 번역한 사람: author5