Ладейная атака
Ладейная атака
На шахматной доске вырезано несколько клеток, координаты которых задаются. Вам следует так разместить наибольшее количество ладей на шахматной доске, чтобы они не били друг друга. Ладья атакует те клетки шахматной доски, которые находятся в одной с ней горизонтали или вертикали. Ладьи нельзя размещать на вырезанных квадратах. Вырезанные клетки не являются преградой для атаки ладей.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит три целых числа: ширина 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.
Выходные данные
Для каждого теста выведите в отдельной строке наибольшее количество ладей, которое можно расположить на доске так, чтобы они не били друг друга.
Пример
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
8 2 3