Майкл и астероиды

Вобщем, условие задачи:

Майкл хочет провести свой космический корабль через опасное астероидное поле в форме решетки N*N (1 <= N <= 500). Решетка содержит K астероидов (1 <= K <= 10,000), которые расположены в узлах решетки.

У Майкла есть мощное оружие, которое способно уничтожить все астероиды в заданной строке или заданном столбце одним выстрелом. Это оружие очень дорогое, и поэтому Майкл хочет использовать его экономно. По заданному расположению астероидов на поле, найдите минимальное количество выстрелов, которое требуется сделать Майклу, чтобы уничтожить все астероиды.

Формат ввода:

• Строка 1: Два целых числа N и K, разделенных одним пробелом

• Строки 2..K+1: Каждая строка содержит два разделенных пробелом числа R и C (1 <= R, C <= N), обозначающие соответственно координаты строки и колонки астероида.

Пример ввода:

3 4
1 1
1 3
2 2
3 2

Детали ввода:

Следующая диаграмма представляет заданную решетку, где 'X' обозначает астероид, а '.' обозначает отсутствие астероида.

X.X
.X.
.X.

Формат вывода:

• Строка 1: Целое число, представляющее минимальное количество выстрелов, которые должен сделать Майкл

Пример вывода:

2

Детали вывода:

Майкл может выстрелить по строке 1, уничтожив астероиды в позициях (1,1) и (1,3), а затем выстрелить по колонке 2, уничтожив астероиды в позициях (2,2) и (3,2).

Ограничение по памяти: 32 Мб. Ограничение по времени: 1 секунда.