시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 52 12 11 34.375%

문제

각 칸에 번호가 붙어 있는 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 크기의 도미노를 놓을 두 칸은 반드시 인접해 있어야 하며, 선으로 분리되어 있는 두 칸을 덮어서는 안 된다. 하나의 칸에 여러 개의 도미노를 놓아서도 안 되며, 반드시 모든 칸을 겹치지 않게 덮는 해를 출력해야 한다. 출력하는 순서는 상관이 없으며, 도미노를 놓는 방법이 둘 이상인 경우 그 중 한 경우만 출력한다.

예제 입력 1

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

예제 출력 1

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

힌트

W3sicHJvYmxlbV9pZCI6IjE4MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWJiZjhcdWIxNzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMwMSBcdWNlNzhcdWM1ZDAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNCBcdWM3ODhcdWIyOTQgTiZ0aW1lcztNIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkMzEwXHVjNWQwXHViMjk0IFx1YmE4NyBcdWFjMWNcdWM3NTggXHVjMTIwXHVjNzc0IFx1YWRmOFx1YjdlY1x1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMxMjBcdWM3NDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1Y2U3OFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWM1ZDAgXHVhZGY4XHViODI0XHVjOWM0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NDAgTj00LCBNPTVcdWM3NzRcdWFjZTAsIDlcdWFjMWNcdWM3NTggXHVjMTIwXHVjNzc0IFx1YWRmOFx1YjgyNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViYWE4XHVjMmI1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RvbWlubzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ0cHg7IHdpZHRoOjI3OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NDQgMSZ0aW1lczsyIFx1YjYxMFx1YjI5NCAyJnRpbWVzOzEgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjg1YyBcdWJhYThcdWI0NTAgXHViMzZlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViMmU4LCBcdWMxMjBcdWM3M2NcdWI4NWMgXHViZDg0XHViOWFjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIzYzRcdWJiZjhcdWIxNzhcdWI4NWMgXHViMzZlXHVjNzQ0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgMVx1YmM4OCBcdWNlNzhcdWFjZmMgMlx1YmM4OCBcdWNlNzhcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjg1YyBcdWIzNmVcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYywgNlx1YmM4OCBcdWNlNzhcdWFjZmMgN1x1YmM4OCBcdWNlNzhcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjg1YyBcdWIzNmVcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNTQ0XHViNzk4XHViMjk0IFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYyBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NDQgXHViYWE4XHViNDUwIFx1YjM2ZVx1Yzc0MCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTSgxJmxlO04sIE0mbGU7MTAwKVx1Yzc3NCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVhY2ZjIE0gXHVjOTExIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWIyOTQgXHVjOWRkXHVjMjE4XHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTggTCgwJmxlO0wmbGU7NSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIExcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWMxMjBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjZTc4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHViNDUwIFx1Y2U3OFx1Yzc0NCBcdWJkODRcdWI5YWNcdWMyZGNcdWQwYTRcdWIyOTQgXHVjMTIwXHVjNzc0XHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHViYzg4XHVkNjM4XHViMjk0IE4mdGltZXM7TSBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHViODVjIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBpXHViYzg4XHVjOWY4LCBcdWM3MDRcdWI4NWNcdWJkODBcdWQxMzAgalx1YmM4OFx1YzlmOCBcdWNlNzhcdWM3NzQgKGotMSkmdGltZXM7TStpIFx1YmM4OFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOJnRpbWVzO00mZGl2aWRlOzJcdWFjMWMgXHVjOTA0XHVjNWQwIFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjk3YyBcdWIxOTNcdWM3NDQgXHViNDUwIFx1Y2U3OFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gMSZ0aW1lczsyIFx1YjYxMFx1YjI5NCAyJnRpbWVzOzEgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjk3YyBcdWIxOTNcdWM3NDQgXHViNDUwIFx1Y2U3OFx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjNzc4XHVjODExXHVkNTc0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YzEyMFx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YjQ1MCBcdWNlNzhcdWM3NDQgXHViMzZlXHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWNlNzhcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIzYzRcdWJiZjhcdWIxNzhcdWI5N2MgXHViMTkzXHVjNTQ0XHVjMTFjXHViM2M0IFx1YzU0OCBcdWI0MThcdWJhNzAsIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNzQ0IFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWFjOGMgXHViMzZlXHViMjk0IFx1ZDU3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YzBjMVx1YWQwMFx1Yzc3NCBcdWM1YzZcdWM3M2NcdWJhNzAsIFx1YjNjNFx1YmJmOFx1YjE3OFx1Yjk3YyBcdWIxOTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YjQ1OCBcdWM3NzRcdWMwYzFcdWM3NzggXHVhY2JkXHVjNmIwIFx1YWRmOCBcdWM5MTEgXHVkNTVjIFx1YWNiZFx1YzZiMFx1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG9taW5vMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDRweDsgd2lkdGg6Mjc4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEb21pbm8iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBjaGVzc2JvYXJkIG9mIHNpemUgbiZ0aW1lczttLiBUaGVyZSBhcmUgYWxzbyBzb21lIGxpbmVzIGRyYXduIG9uIGl0LiBFYWNoIGxpbmUgc2VwYXJhdGVzIHR3byBhZGphY2VudCBmaWVsZHMuIFlvdSBhcmUgZ29pbmcgdG8gcHV0IGRvbWlub2VzIG9uIHRoZSBjaGVzc2JvYXJkLiBFYWNoIGRvbWlubyBjb3ZlcnMgdHdvIGFkamFjZW50IGZpZWxkcy4gWW91IGNhbiBwdXQgYSBkb21pbm8gb24gdHdvIGFkamFjZW50IGZpZWxkcyBvbmx5IGlmIHRoZXkgYXJlIG5vdCBzZXBhcmF0ZWQgYnkgYSBsaW5lLiBZb3VyIHRhc2sgaXMgdG8gZmluZCBzdWNoIGFuIGFycmFuZ2VtZW50IG9mIGRvbWlub2VzIG9uIHRoZSBjaGVzc2JvYXJkLCB0aGF0IGVhY2ggZmllbGQgaXMgY292ZXJlZCBieSBleGFjdGx5IG9uZSBkb21pbm8uIFlvdSBjYW4gYXNzdW1lIHRoYXQgZm9yIGVhY2ggaW5wdXQgZGF0YSB0aGVyZSBpcyBhIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RvbWlubzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ0cHg7IG9wYWNpdHk6MC45OyB3aWR0aDoyNzhweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgYW4gaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzLCBuIGFuZCBtLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UgLSBuIGlzIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgbSBpcyB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgb2YgdGhlIGNoZXNzYm9hcmQsIDEgJmxlOyBuLG0gJmxlOyAxMDAsIG4mbWlkZG90O20gaXMgZXZlbi4gVGhlIGZpZWxkIG9mIHRoZSBjaGVzc2JvYXJkIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbiZtaWRkb3Q7bS4gVGhlcmUgaS10aCBmaWVsZCAoZnJvbSB0aGUgbGVmdCkgaW4gdGhlIGotdGggcm93IChmcm9tIHRoZSB0b3ApIGhhcyBudW1iZXIgKGotMSkmbWlkZG90O20gKyBpIChmb3IgMSAmbGU7IGkgJmxlOyBtLCAxICZsZTsgaiAmbGU7IG4pLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgb25lIHBvc2l0aXZlIGludGVnZXIgbCwgMCAmbGU7IGwgJmxlOyA1MDAwLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbCBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgaSsyLW5kIGxpbmUgY29udGFpbnMgaW50ZWdlcnMgcDxzdWI+aTxcL3N1Yj4gYW5kIHE8c3ViPmk8XC9zdWI+IChmb3IgaSA9IDEsLi4uLGwpLCB3aGVyZSAxICZsZTsgcDxzdWI+aTxcL3N1Yj4scTxzdWI+aTxcL3N1Yj4gJmxlOyBuJm1pZGRvdDttLCBwaSBhbmQgcWkgYXJlIG51bWJlcnMgb2YgdHdvIGFkamFjZW50IGZpZWxkcy4gSXQgcmVwcmVzZW50cyBhIGxpbmUgYmV0d2VlbiBmaWVsZHMgbnVtYmVyIHA8c3ViPmk8XC9zdWI+IGFuZCBxPHN1Yj5pPFwvc3ViPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBvdXRwdXQgc2hvdWxkIGNvbnNpc3Qgb2YgKG4mbWlkZG90O20pXC8yIGxpbmVzIGRlc2NyaWJpbmcgYW4gYXJyYW5nZW1lbnQgb2YgdGhlIGRvbWlub2VzLCBvbmUgZG9taW5vIHBlciBsaW5lLiBFYWNoIG9mIHRoZXNlIGxpbmVzIHNob3VsZCBjb250YWluIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U6IG51bWJlciBvZiB0d28gYWRqYWNlbnQgZmllbGRzIGNvdmVyZWQgYnkgYSBkb21pbm8uIFRoZSBkb21pbm9lcyBtYXkgYmUgZGVzY3JpYmVkIGluIGFueSBvcmRlci4gSWYgdGhlcmUgYXJlIHNldmVyYWwgc29sdXRpb24sIHlvdXIgc2hvdWxkIGZpbmQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RvbWlubzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ0cHg7IG9wYWNpdHk6MC45OyB3aWR0aDoyNzhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2005 P2번

  • 문제를 번역한 사람: author5