Поверніть ліворуч
Таро отримав водійські права з великими зусиллями під час навчання в університеті, але, на жаль, у нього не було можливості водити машину. Зрештою, він отримав золоте посвідчення.
Одного дня він і його друзі запланували поїздку до Кіото разом з вами. Наприкінці зустрічі вони вирішили їхати машиною, але виникла велика проблема: ніхто з його друзів не вмів водити. Тому Таро довелося стати водієм.
Настав день від'їзду. Він збирається водити, але ніколи не повертає праворуч через страх перетнути зустрічну смугу (зверніть увагу, що в Японії машини рухаються ліворуч). Крім того, він не може розвернутися через брак навичок. Автомобіль оснащений навігаційною системою, але система не може знайти маршрут без правих поворотів. Тому він попросив вас: "Я ненавиджу праві повороти, тому чи не могли б ви написати програму, щоб знайти найкоротший маршрут лише з лівими поворотами до пункту призначення, використовуючи карту доріг, взяту з цієї навігаційної системи?"
Вхідні дані
Вхідні дані складаються з кількох наборів. Перша строка вхідних даних містить кількість наборів. Кожен набір описується у форматі нижче:
m n
name_1 x_1 y_1
...
name_m x_m y_m
p_1 q_1
...
p_n q_n
src dst
m — це кількість перехресть. n — це кількість доріг. namei — це назва i-го перехрестя. (x_i, y_i) — це цілі координати i-го перехрестя, де позитивна x йде на схід, а позитивна y йде на північ. p_j і q_j — це назви перехресть, які представляють кінцеві точки j-ї дороги. Усі дороги двосторонні та або вертикальні, або горизонтальні. src і dst — це назви вихідного та кінцевого перехресть відповідно. Ви можете припустити всі наступні умови:
2 ≤ m ≤ 1000, 0 ≤ x_i ≤ 10000, і 0 ≤ yi ≤ 10000;
кожна назва перехрестя є послідовністю з одного або більше алфавітних символів довжиною не більше 25 символів;
жодні перехрестя не мають однакових координат;
жодна пара доріг не має спільних точок, окрім їхніх кінцевих точок;
жодна дорога не має перехресть посередині;
жодна пара перехресть не має більше однієї дороги;
Таро може почати рух у будь-якому напрямку; і
вихідне та кінцеве перехрестя різні.
Зверніть увагу, що може бути випадок, коли перехрестя з'єднане з менше ніж трьома дорогами у вхідних даних; карта доріг може не включати менші дороги, які не підходять для не місцевих людей. У такому випадку ви все одно повинні розглядати їх як перехрестя, коли проїжджаєте через них.
Вихідні дані
Для кожного набору даних надрукуйте, скільки разів щонайменше Таро потрібно проїхати через перехрестя, коли він їде маршрутом найкоротшої відстані без правих поворотів. Вихідне та кінцеве перехрестя повинні вважатися "пройденими" (тобто повинні бути враховані), коли Таро починає з вихідного або прибуває до кінцевого перехрестя. Також зверніть увагу, що може бути більше одного можливого найкоротшого маршруту. Надрукуйте "неможливо", якщо немає маршруту до пункту призначення без правих поворотів.