Pe o tabla patrata de dimensiune NxN se afla p cai albi si un cal negru. Pozitiile pe care se afla caii sunt cunoscute. Mutarile efectuate de un cal sunt cele de la jocul de sah, asa cum arata figura de mai jos (calul aflat in pozitia marcata cu C poate efectua una dintre cele 8 mutari marcate cu X, cu conditia ca pozitia finala sa fie in interiorul tablei de joc).

Scrieti un program care sa determine numarul total minim de mutari efectuate de caii albi, astfel incat calul negru sa fie blocat in pozitia sa initiala, in ipoteza in care calul negru nu efectueaza mutari.

Date de intrare

Fisierul de intrare cai1.in are urmatoarea structura:
Linia 1: contine numerele naturale N si p, separate printr-un spatiu, cu semnificatia din enunt;
Linia 2: contine 2 numere naturale L si C, reprezentand pozitia calului negru (linia L si coloana C);
Pe urmatoarele p linii se afla cate doua numere naturale separate prin spatiu L_i si C_i, reprezentand pozitiile initiale ale cailor albi.

Date de iesire

Fisierul de iesire cai1.out va contine o singura linie pe care va fi scris un numar natural reprezentand numarul total minim de mutari efectuate de caii albi astfel incat calul negru sa fie blocat in pozitia sa initiala.

Restrictii

Exemple

prof. Alin Burta
Colegiul National "B.P. Hasdeu" Buzau
Contact: allbu2003@yahoo.com