Хексзмії у хексболоті
Хексболото - це дивний тип болота, вимощеного правильними шестикутними ямками. Хексзмії повзають у ньому, будучи адаптованими до навколишнього середовища. Вони являють собою ланцюжок правильних шестикутників, кожен з яких строго повністю поміщається в одну шестикутну ямочку.
Хексзмії переміщують свої секції з ямок у яких вони знаходяться, на сусідні. Щоб не зламати своє тіло, частини хексзмій, які були сусідніми до здійснення переміщення, залишаються сусідніми і після. Коли рухається одна з секцій, то секції, що прилягають до неї, сприяють руху і тому не можуть рухатись у той же самий час. Довільне число секцій, ніякі дві з яких не є сусідніми, можуть переміщуватись одночасно.
Можно помітити, що хексзмія може пересувати свої секції, які знаходяться на кінцях, у одну з двох ямок, а проміжні секції лише в одну, якщо така існує.
Наприклад, у випадку відсутності перешкод, хексзмії можуть повзти вперед, звиваючи своє тіло, як показано на Рисунку 1, зліва направо. На рисунку змія у кожен момент часу переміщує чотире свої частини тіла з вісьми, і пересуває усе своє тіло вперед на довжину однієї ямки після чотирьох кроків руху. Насправді, вони набагато краще повзають боком, ніби рослини, що в'ються.
Рисунок1: Повзання вперед
Їхня кожа настільки липка, що якщо дві секції які спочатку не були сусідніми, попадуть у сусідні ямки (Рисунок 2), то вони склеяться разом і змія помре. Дві секції не можуть поміститись у одній ямці. Це звичайно ж сковує пересування змії. Іноді їм приходиться прикласти деякі зусилля, щоб дістати шматок іжі, навіть якщо він знаходиться у ямці поруч з головою.
Рисунок 2: Смертельний випадок
І там і тут на хексболоті знаходяться скали. Каждая скала поміщається у точності в одну ямку. Кожа хексзмій не прилипає до скаль, проте змії не можуть заповзати на них. І хоча ямки зі скелями обмежують пересування змій, вони у свою чергу добре знають географію місцевості і можуть планувати своє пересування по найкоротшому маршруту.
Вас призначили керівником групи вчених, яка займається проведенням наукови досліджень змій на цьому болоті. Вам потрібно завершити розпочате дослідження, але не на будь-яку шкоду. Ваша задача - оцінити як швидко хексзмія, яка харчується людьми, перемістить свою голову (першу секцію) у позицію болота, де знаходиться вчений. Секції тіла змії крім голови безвредні, і вчений, одітий у хай-тек антиприлипаючий костюм, може знаходитись у довільній з секцій тіла у одній ямці.
Вхідні дані
Вхідні дані складаються з декількох тестів, останній рядок містить один нуль. Кількість тестів не перевищує 10.
Кожен тест має наступний формат.
кількість секцій у змії (=n)
x1 y1
x2 y2
...
xn yn
кількість скал на болоті (=k)
u1 v1
u2 v2
...
uk vk
X Y
Перший рядок кожного тесту містить число n - кількість секцій у змії, воно рівне 2 або більше, але ніколи не перевищує 8. Кожен з наступних n рядків містит x та y координати секції змії. Рядки описують початкове положення секцій у порядку від голови до хвоста.
Наступний рядок задає кількість скал k у болоті, це число не від'ємне і не перевищує 100. Кожен з наступних k рядків містить два цілих числа u та v - положення скали.
Останній рядок містить два цілих числа X та Y - позиція, куди необхідно приповзти змії. Голова змії спочатку тут не знаходиться.
Усі значення координат x, y, u, v, X та Y лежать в інтервалі від -999999 до 999999 включно. Два числа у рядку відокремлено одним пропуском. У вхідних даних не зустрічаються інші символи, крім як десяткові цифри, знак минус та пропуски, що їх розділяють. Система координат, яка кодує позиції, показана на Рисунку 3.
Рисунок 3: Система координат
Вихідні дані
Для коного тесту вивести рядок, який містить ціле число - найменшу кількість крокі, необхідних змії пересунути свою голову у заданую позицію. Вихідні рядки не повинні містити ніяких інших символів.
Вважайте, що хексзмії можуть знайти розв'язок не більш ніж за 20 колків.