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