Na kwadratowej planszy, składającej się z NxN pól ustawiono M dział laserowych. Każde takie działo strzela w czterech kierunkach naraz: pionowo do góry, pionowo do dołu, poziomo w prawo i poziomo w lewo, a strzał dociera zawsze do końca planszy niszcząc wszystko po drodze. Niestety rozmieszczenie tych dział było bardzo źle przemyślane, ponieważ strzelając z niektórych miejsc, może się zdarzyć tak, że się zniszczy jakieś działa stojące na drodze lasera. Napisz program, który stwierdzi z ilu dział można oddać bezpieczne strzały, czyli takie, które nie zniszczą żadnego innego działa.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite N i M (1 ≤ N ≤ 50000, 1 ≤ M ≤ 1 000 000), oznaczające odpowiednio rozmiar planszy i liczbę dział laserowych. W kolejnych M wierszach są opisy dział. Jeden opis składa się z dwóch liczb naturalnych X i Y (1 ≤ X,Y ≤ N), będących współrzędnymi pola, na którym stoi działo. Możesz założyć, że żadne dwa nie stoją na jednym polu.
Twój program ma wypisać na standardowe wyjście liczbę dział, które po oddaniu strzału nie zniszczą niczego.
Dla danych wejściowych:
5 7 4 3 1 5 3 3 3 5 2 4 3 2 5 1
poprawną odpowiedzią jest:
2
Wyjaśnienie: Bezpiecznie można strzelić tylko z dział na współrzędnych (5,1) i (2,4).
[Zgłoś rozwiązanie] [Moje zgłoszenia]