Шахи з "Гаррі Поттера"
Багатьох вразила сцена з величезними шахами в одному з фільмів про Гаррі Поттера. Вона показала, що гра в шахи теж може бути небезпечною для життя. Справа в тому, що там фігури вбивають по-справжньому, але виключно в рамках шахових правил, звісно.
У фігур повно вільного часу. Їм нудно просто стояти і чекати, поки хтось не наважиться пограти з ними. Тому, час від часу, вони грають самі із собою. Але виникла невелика проблема. Кожен раз, коли одну з фігур вбивають нищівним ударом меча, вона розлітається на шматки і залишається лежати на дошці. Це заважає іншим фігурам пересуватися. Тому, вони змушені просити фею з чарівним пилососом (якій теж, відверто, нічого робити) допомагати їм, і засмоктувати залишки фігур, які вибули з гри. Пилосос доволі об'ємний, хоч і чарівний. Він може пересуватися тільки по порожніх клітинах, що мають спільні сторони. Щоб "прибирання" проходило як омога швидше, фея просить Вас визначити мінімальну кількість клітин шахової дошки, які їй потрібно пройти, щоб опинитися в клітці з убитої фігурою. Спочатку фея знаходиться за межами дошки.
Вхідні дані Перший рядок містить кількість фігур (2 ≤ n ≤ 31), що знаходяться в даний момент на дошці, і координати клітини, в якій відбулося вбивство. У наступних n рядках подаються координати фігур, перша з яких містить вертикаль (від a до h), а друга горизонталь (від 1 до 8).
Вихідні дані
Виведіть мінімальну кількість клітин, включаючи клітку з убитою фігурою, яку феї потрібно пройти. Якщо ж добратися неможливо, то виведіть "-1" (без лапок).