Marcin Kubica
Tłumaczenie

Knights

Dana jest szachownica o wymiarach n times n , z której usunięto pewną liczbę pól. Należy wyznaczyć maksymalną liczbę skoczków (koników) szachowych, które można ustawić na pozostałych polach szachownicy tak, żeby żadne dwa skoczki nie atakowały się nawzajem.

Rysunek 1: Skoczek umieszczony w polu S atakuje pola oznaczone przez x.

Zadanie

Napisz program, który:

wczyta opis szachownicy z usuniętymi polami z pliku tekstowego kni.in,
wyznaczy maksymalną liczbę wzajemnie nie atakujących się skoczków szachowych, które można ustawić na tej szachownicy,
zapisze wynik w pliku tekstowym kni.out.

Wejście

W pierwszym wierszu pliku tekstowego kni.in znajdują się dwie liczby całkowite n i m, gdzie 1 leq n leq 200

. Liczba n oznacza rozmiar szachownicy, a m oznacza liczbę usuniętych pól.

W każdym z kolejnych m wierszy jest zapisana para liczb naturalnych x i y, gdzie 1 leq x,y leq n , oddzielonych pojedynczym odstępem. Są to współrzędne usuniętych pól. Lewy górny róg szachownicy ma współrzędne (1,1), natomiast prawy dolny róg ma współrzędne (n,n). Pola nie powtarzają się.

Wyjście

Plik tekstowy kni.out powinien zawierać dokładnie jeden wiersz, zawierający pojedynczą liczbę całkowitą równą maksymalnej liczbie wzajemnie nie atakujących się skoczków, które można ustawić na zadanej szachownicy.

Przykład

Dla pliku wejściowego kni.in

3 2
1 1
3 3

poprawną odpowiedzią jest plik wyjściowy kni.out