Шестикутні шляхи

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

Для опису області необхідно промоделювати її карту. В ACM нещодавно виявили, що трикутні та прямокутні моделі областей є недостатніми, тому вирішили використовувати шестикутники для опису карт. Клітинки правильної шестикутної сітки (наприклад, сот) можна нумерувати, починаючи з $1$ (у довільній клітинці) і рухатись по спіралі до інших клітинок. Таким чином, кожна комірка однозначно ідентифікується своїм номером. І навпаки, кожне додатнє ціле число визначає одну комірку.

Дві клітинки називаються сусідніми, якщо вони мають одну спільну сторону. У нескінченній структурі кожна комірка має рівно шість сусідів. Наприклад, комірка номер $2$ є сусідньою з $1$, $3$, $7$, $8$, $9$ та $10$. Шестикутний шлях — це непорожня послідовність комірок, у якій кожна з них (крім останньої) є сусідньою до наступної. Шестикутний шлях між двома комірками $X$ та $Y$ — це шлях, у якому $X$ — перша комірка послідовності, а $Y$ — остання. Довжиною шляху називається кількість комірок у ньому мінус один. Довжина шляху являє собою кількість кроків, необхідних для проходження усього маршруту.

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