Дивний кінь

Limits: 2 sec., 512 MiB

Вінниця. Ніч. Дивний кінь ходить по гуртожитку Вінницького національного технічного університету.

Гуртожиток представляє собою квадрат розміром \(n\times n\), який складається з \(n^2\) квадратних кімнат розміром \(1 \times 1\). Верхня ліва кімната має координати \((1, 1)\), нижня права — \((n, n)\). Кінь сумує і тому хоче завітати до кімнати своїх друзів. Однак злі вахтери хочуть не дозволити йому це зробити. Усі вони сидять у різних кімнатах, і жоден із них не є в кімнаті, де зараз стоїть кінь. Якщо після свого ходу кінь опиниться в одній кімнаті з вахтером, то наш герой буде вигнаний з гуртожитку. Проте, якщо протягом свого ходу кінь проскакував через кімнату з вахтером, той не міг стримати страху і покидав свою роботу.

Оскільки кінь дуже хоче побачити своїх друзів, то він хоче дійти до їхньої кімнати за мінімальну кількість ходів.

Input

У першому рядку задано два цілі числа \(n\) і \(k\) — довжина гуртожитку й кількість вахтерів у ньому відповідно.

У другому рядку задано два цілих числа \(sx\), \(sy\) — координати кімнати, де початково стоїть кінь.

У третьому рядку задано два цілих числа \(fx\), \(fy\) — координати кімнати, де є друзі коня (координати кімнати можуть збігатися з координатами кімнати коня).

У наступних \(k\) рядках задано по два цілих числа \(x_i\), \(y_i\) — координати кімнат, де сидять вахтери.

Output

Якщо кінь зможе дістатися до кімнати друзів, то виведіть одне ціле число — мінімальну кількість кроків, які йому необхідно для цього.

Інакше виведіть число -1.

Constraints

\(1 \le n \le 50\),

\(0 \le k \le 10\),

\(1 \le sx, sy, fx, fy, x_i, y_i \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 0 1 1 3 2	1

Input (stdin) сopy	Output (stdout) сopy
3 1 1 1 3 2 3 2	5

Input (stdin) сopy	Output (stdout) сopy
3 0 1 1 3 3	4

Input (stdin) сopy	Output (stdout) сopy
3 2 1 1 3 3 3 2 2 3	-1