Задачі
Ладейна атака
Ладейна атака
На шаховій дошці вирізано декілька клітин, координати яких задаються. Вам слід так розмістити найбільшу кількість ладей на шаховій дошці, щоб вони не били одна одну. Ладдя атакує ті клітини шахової дошки, що знаходяться в одній з нею горизонталі або вертикалі. Ладді не можна розташовувати на вирізаних квадратах. Вирізані клітини не є перешкодою для атаки ладей.
\InputFile
Складається з декількох тестів. Перший рядок кожного тесту містить три цілі числа: ширина $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$.
\OutputFile
Для кожного тесту виведіть в окремому рядку найбільшу кількість ладей, яку можна розташувати на дошці так, щоб вони не били одна одну.
Вхідні дані #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
Пояснення: Другий рядок порожній, оскільки кількість вирізаних квадратів на дошці в першому тесті дорівнює 0