Божевільний Король

Король Петро живе в королівстві $A$, а його дочка в королівстві $B$. Король отримав листа, в якому повідомлялося, що його дочка народила дитину. Король неймовірно хоче побачити свого онука! На жаль, це буде не так просто.

Королівства $A$ і $B$ розділені лісом. У лісі багато ворогів, і король не прагне їх зустріти. Якщо вони нападуть на короля на шляху до королівства $B$, то він ніколи більше не побачить свого онука і дочку через летальні наслідки.

Таємна рада короля володіє інформацією про розташування ворогів, що полегшує завдання для короля. З невідомої причини ліс є шахівницею розміром M \times N. ($M$ — це кількість рядків, а $N$ — кількість стовпців). $N$, M \leq 100 — додатні цілі числа.

Вороги короля можуть їздити на конях, як показано на малюнку. Зазвичай коні рухаються (або стрибають) так у шахах. На жаль, король не може взяти літак з точки $A$ до точки $B$, тому що його ще не винайшли. Тому він рухається так само, як шаховий король (див. малюнок для деталей).

Король не може перейти на клітинку $X$, якщо на цій клітинці знаходиться кінь ворога. Поки король рухається, коні не рухаються, але якщо хоча б один кінь може досягти клітинки $X$ за один хід, то король не може перейти на цю клітинку (за винятком випадку, коли клітинка $X$ є або королівством $A$, або $B$).

Ви є начальником відділу електронної розвідки королівства $A$ (до речі, комп'ютери вже винайдені). І вас просять знайти довжину найкоротшого маршруту з королівства $A$ до $B$, оскільки король дуже хоче побачити свого онука.