<PREV Problem:
Solved by 107 users: ...


Time limit = 5

Many years ago king Artur and knights of The Round Table used to celebrate New Year together. In honour of that conventions table game Camelot for one player was developed.

In beginning King and Knights are placed on the chessboard. Size of board is NxN. King can be moved to any adjacent square:

Possible moves of king
The knight's movement looks like the letter "L":

Possible moves of knight

If king and knight stay on one square then player can move knight together with king in one move.

Player can place any amount of pieces into one square. The goal is to move all pieces to one square.

Input First line: size of the board N (4 ≤ N ≤ 50) and M (M ≤ 100) — amount of knights. Second line: coordinates of king and in next M lines there is coordinates of knights (coordinates is a pair of numbers in the interval [1, N]).

Output Minimal amount of moves player have to do to move all pieces to one square.

8 4
4 4
1 3
1 8
8 1
8 8

Andrey Ulanov (the idea is taken from Kursk regional contest 2000).
May, 16 th, 2003

<PREV | Problem set | Search related messages | NEXT>

© acm.mipt DevGroup
The page was generated in 220ms

SW soft NIX
ID =