Робочий стіл

На робочому столі операційної системи знаходиться $N$ ярликів, кожен з яких заданий цілими координатами $x$ і $y$, а також іменем. Ім'я кожного ярлика складається з малих латинських літер ($a$–$z$). Вам потрібно перейти з поточно вибраного ярлика $S$ до цільового ярлика $F$ за допомогою клавіатури, зробивши якомога менше натискань клавіш. Переміщення відбувається за допомогою літерних клавіш $a$–$z$ або стрілок "$\uparrow$", "$\downarrow$", "$\leftarrow$", "$\to$".

При використанні літерних клавіш вибір змінюється за такими правилами:

1. Якщо існують ярлики, імена яких починаються з натиснутої літери, і один із них наразі вибраний, вибір переходить до наступного ярлика (у лексикографічному порядку серед тих, що починаються з цієї літери; після останнього переходить знову до першого з такою літерою). Наприклад, якщо є ярлики $a$, $ab$, $b$, при натисканні $a$ вибір перемикатиметься тільки між $a$ та $ab$.

2. Якщо ім'я поточного ярлика не починається з натиснутої літери, вибір переходить до лексикографічно найменшого ярлика, що починається з цієї літери.

3. Якщо немає жодного ярлика, що починається з цієї літери, нічого не відбувається.

При використанні клавіш-стрілок вибір переходить до найближчого ярлика (за евклідовою відстанню) у напрямку стрілки, в межах прямокутного сектора, що виходить із поточного ярлика. Бісектриса цього сектора співпадає з напрямком стрілки. Якщо ярлик лежить на межі сектора, він належить до верхнього/нижнього сектору (а не лівого чи правого). Якщо у секторі немає жодного ярлика, вибір не змінюється. Якщо декілька ярликів знаходяться на однаковій мінімальній відстані, обирається той, у кого менше $x$; якщо знову рівність, обирається той, у кого менше $y$.

Наприклад, якщо наразі вибраний ярлик $a$ (див. рисунок), то переходи при натисканні стрілок виглядають так:

1. Стрілка "$\leftarrow$": Вибір переходить до ярлика $b$, який є найближчим у цьому секторі. Ще одне натискання "$\leftarrow$" вибере ярлик $c$.

2. Стрілка "$\uparrow$": У цьому секторі знаходяться ярлики $d$ та $e$. Вибір переходить до $d$, як до ближчого.

3. Стрілка "$\to$": У цьому секторі є лише ярлик $g$, тому вибір переходить до нього.

4. Стрілка "$\downarrow$": Ярлики $f$ та $h$ знаходяться на однаковій відстані від $a$. Вибирається $h$, оскільки у нього менше $x$. Ще одне натискання "$\downarrow$" залишає вибір на $h$, оскільки у нижньому секторі інших ярликів немає.

Напишіть програму DESKTOP, яка за назвами та координатами ярликів обчислює мінімальну кількість натискань клавіш, необхідних для переходу від ярлика $S$ до ярлика $F$.