eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Шахматы

Шахматы

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Петя и Вася играют в следующую игру. Сначала Вася расставляет на шахматной доске размера n×m слонов произвольным образом. После этого Петя должен расставить на свободные клетки ладей так, чтобы, во-первых, никакие две ладьи не били друг друга, и, во-вторых, никакая ладья не стояла под боем слона.

Петя хочет расставить максимально возможное количество ладьей. Помогите ему.

Входные данные

В первой строке находятся два числа n и m (1n, m100) - количество строк и столбцов соответственно. Во второй строке находится одно число k (0kn·m) - количество слонов. В следующих k строках заданы местоположения слонов - номер строки и столбца соответственно.

Выходные данные

В первой строке выведите максимальное количество ладьей, которое может расставить Петя. В следующих строчках выведите описания положения ладей в том же формате, что и во входном файле.

Пример

Входные данные #1
2 2
1
2 2
Выходные данные #1
2
2 1
1 2