Nered

Στο κοντινό νηπιαγωγείο έφτιαξαν πρόσφατα ένα ελκυστικό παιχνίδι δύναμης και ευκινησίας που τα παιδιά το λατρεύουν.
Η επιφάνεια για το παιχνίδι είναι μια μεγάλη επίπεδη περιοχή χωρισμένη σε ~N \times N~ τετράγωνα.
Τα παιδιά βάζουν μεγάλα σπογγώδη σημάδια στην επιφάνεια. Οι πλευρές των κύβων έχουν το ίδιο μήκος με τις πλευρές των τετραγώνων. Όταν ένας κύβος τοποθετείται στην επιφάνεια, οι πλευρές του ευθυγραμμίζονται με κάποιο τετράγωνο. Ένας κύβος μπορεί να τοποθετηθεί και σε άλλο κύβο.
Τα παιδιά απολαμβάνουν να χτίζουν οχυρά και να τα κρύβουν, αλλά πάντα αφήνουν πίσω τους ένα τεράστιο χάος. Εξαιτίας αυτού, πριν κλείσουν το νηπιαγωγείο, οι δάσκαλοι αναδιατάσσουν όλους τους κύβους έτσι ώστε να καταλαμβάνουν ένα ορθογώνιο στην επιφάνεια, με ακριβώς έναν κύβο σε κάθε τετράγωνο στο ορθογώνιο.
Σε μία κίνηση, ένας κύβος αφαιρείται από την κορυφή ενός τετραγώνου προς την κορυφή οποιουδήποτε άλλου τετραγώνου.
Γράψτε ένα πρόγραμμα που, δεδομένης της κατάστασης της επιφάνειας, να υπολογίζει τον μικρότερο αριθμό κινήσεων που απαιτούνται για να διατάξουν όλους τους κύβους σε ένα ορθογώνιο.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~N~ και ~M (1 \le N \le 100, 1 \le M \le N^2)~, τις διαστάσεις της επιφάνειας και τον αριθμό των κύβων που βρίσκονται αυτή τη στιγμή στην επιφάνεια.
Κάθε μία από τις ακόλουθες γραμμές ~M~ περιέχει δύο ακέραιους αριθμούς ~R~ και ~C (1 \le R, C \le N)~, τις συντεταγμένες του τετραγώνου που περιέχει τον κύβο.

Έξοδος

Τυπώστε τον μικρότερο αριθμό κινήσεων. Θα υπάρχει πάντα μια λύση.

Παραδείγματα

input

3 2
1 1
1 1

output

1

Επεξήγηση του 1ου παραδείγματος:

Αρκεί να μετακινήσετε έναν από τους κύβους από το ~(1,\;1)~ στο ~(1,\;2)~ ή στο ~(2,\;1)~.

input

4 3
2 2
4 4
1 1

output

2

input

5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3

output

3

Επεξήγηση του 3ου παραδείγματος:

Ένας κύβος μετακινείται από το ~(2,\;3)~ στο ~(3,\;3)~, από το ~(4,\;2)~ στο ~(2,\;5)~ και από το ~(4,\;4)~ στο ~(3,\;5)~.