Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări.
Parcul are forma unui pătrat cu latura de n metri şi este înconjurat de un gard care are exact două porţi. Proiectanţii de la Primărie au realizat o hartă a parcului şi au trasat pe hartă un caroiaj care împarte parcul în nxn zone pătrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice pătratice cu n linii şi n coloane. Liniile şi respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor pătrate de latură 1 metru. O astfel de zonă poate să conţină un copac sau este liberă.
Edilii oraşului doresc să paveze cu un număr minim de dale pătrate cu latura de 1 metru zonele libere (fără copaci) ale parcului, astfel încât să se obţină o alee continuă de la o poartă la alta.
Cerinţă
Scrieţi un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.
Date de intrare
Fişierul de intrare alee.in conţine pe prima linie două valori naturale n şi m separate printr-un spaţiu, reprezentând dimensiunea parcului, respectiv numărul de copaci care se găsesc în parc. Fiecare dintre următoarele m linii conţine câte două numere naturale x şi y separate printr-un spaţiu, reprezentând poziţiile copacilor în parc (x reprezintă linia, iar y reprezintă coloana zonei în care se află copacul). Ultima linie a fişierului conţine patru numere naturale x1 y1 x2 y2, separate prin câte un spaţiu, reprezentând poziţiile celor două porţi (x1, y1 reprezintă linia şi respectiv coloana zonei ce conţine prima poartă, iar x2, y2 reprezintă linia şi respectiv coloana zonei ce conţine cea de a doua poartă).
Date de ieşire
Fişierul de ieşire alee.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă numărul minim de dale necesare pentru construirea aleii.
Restricţii
1 ≤ n ≤ 175
1 ≤ m < n*n
Aleea este continuă dacă oricare două plăci consecutive au o latură comună.
Aleea începe cu zona unde se găseşte prima poartă şi se termină cu zona unde se găseşte cea de a doua poartă.
Poziţiile porţilor sunt distincte şi corespund unor zone libere.
Pentru datele de test există întotdeauna soluţie.
Exemple
alee.in
alee.out
Explicaţii
8 6
2 7
3 3
4 6
5 4
7 3
7 5
1 1 8 8
15
O modalitate de a construi aleea cu număr minim de dale este: OOO-----
--OO--x-
--xO----
---OOx--
---xO---
----OO--
--x-xOO-
------OO
(cu X am marcat copacii, cu - zonele libere, iar cu O dalele aleii).