Шахи з "Гаррі Поттера"#3296
Багатьох людей вразила величезна шахова сцена у фільмі про Гаррі Поттера. Вона зробила шахові партії грандіозними та магічними. У цій історії шахові фігури іноді грають між собою, коли мають вільний час і їм набридає чекати на гравців.
Однак є одна невеличка проблема: щоразу, коли фігуру захоплюють, вона не залишає дошку одразу, блокуючи шлях для інших фігур. Щоб очистити дошку, вони просять фею з чарівним пилососом забрати захоплені фігури з їхніх клітин. Пилосос доволі громіздкий, навіть якщо він і чарівний, і може рухатися лише порожніми клітинами, які мають спільний бік.
Щоб прибирання тривало якомога швидше, фея просить вас визначити мінімальну кількість клітин, через які вона повинна пройти (включно з клітиною із захопленою фігурою), щоб дістатися до місця захоплення. Спочатку фея знаходиться поза шахівницею.
Перший рядок містить кількість фігур (2 \leq n \leq 31), що наразі на дошці, та координати клітини, де сталося захоплення. Наступні рядків містять координати фігур. Перший символ — вертикаль (від до ), другий — горизонталь (від до ).
Виведіть мінімальну кількість клітин, включаючи клітину із захопленою фігурою, через які фея повинна пройти. Якщо потрапити до цільової клітини неможливо, виведіть .
Приклад 1