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

Ладейная атака

Ладейная атака

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

На шахматной доске вырезано несколько клеток, координаты которых задаются. Вам следует так разместить наибольшее количество ладей на шахматной доске, чтобы они не били друг друга. Ладья атакует те клетки шахматной доски, которые находятся в одной с ней горизонтали или вертикали. Ладьи нельзя размещать на вырезанных квадратах. Вырезанные клетки не являются преградой для атаки ладей.

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

Состоит из нескольких тестов. Первая строка каждого теста содержит три целых числа: ширина rows и длина cols~(1 \le rows, cols \le 300) доски в клетках, а также количество вырезанных клеток cuts. Следующая строка содержит список (x, y) координат вырезанных клеток, разделенных пробелом. Список имеет вид x_1~y_1~x_2~y_2~x_3~y_3 ... x_{cuts}~y_{cuts}. Известно, что 0 \le x_i \le rows - 1, 0 \le y_i \le cols - 1.

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

Для каждого теста выведите в отдельной строке наибольшее количество ладей, которое можно расположить на доске так, чтобы они не били друг друга.

Пример

Входные данные #1
8 8 0

3 3 6
0 0 1 0 1 1 2 0 2 1 2 2
3 3 3
0 0 1 2 2 2
Выходные данные #1
8
2
3