Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Space

Задача Space

Орбітальна станція являє собою куб розмірами n*n*n, що розділений переборками на одиничні відсіки. Кожна переборка має люк. Між деякими  парами відсіків є прямий зв'язок (телепорт), а деякі відсіки завантажені приладами, причому телпортів такі відсіки не мають .Космотнавт знаходиться  в одному з вільних відсіків і бажає перейти в інший вільний відсік. Яку мінімальну кількість люків він має пройти для цього, не заходячи в жоден з відсіків, що завантаженіі приладами? Вважається, що при телепортації космонавт не проходить ні через один люк.

Технічні умови

Ви вводите з клавіатури розмір станції n (1<=n<=50), кількість телепортів K, кількість загромаджених відсіків L,  (0<=K,L<=500), потім K груп по 6 чисел - координати відсіків, з'єднаних телепортом, потім L груп по 3 числа - координати зайнятих відсіків, потім координати космонавта та координати відсіку,  куди він направляється. Всі дані вводяться через пропуск в одну стрічку. Ви виводите на екран шукану мінімальну кількість люків, якщо космонавт потрапити у заданий відсік не зможе, виводить -1.
Приклад

Введення 5 2 6 1 3 3 2 3 2 4 4 4 1 4 3 4 1 1 3 5 4 1 2 4 5 3 2 5 5 5 2 4 1 2 4 2 5 5 4 
Виведення 4


Задача Space

Орбитальная станция представляет собой куб размером n*n*n, раздeлеленный переборками на единичные отсеки. В каждой переборке имеется люк. Между некоторыми парами отсеков имеется прямое сообщение (телепорт), а некоторые отсеки заняты приборами, при этом загруженые отсеки не имеют телепортов. Космонавт находится в одном из свободных отсеков и хочет перейти в другой свободный отсек. Какое минимальное количество люков он должен пройти для этого, не заходя ни в один отсек, занятый приборами? Считается, что при телепортировании космонавт не проходит ни одного люка.

Технические условия
Программа читает с клавиатуры размер станции n (1<=n<=50), количество телепортов K , количество занятых отсеков L (0<=K,L<=500), затем K групп по 6 чисел - координаты отсеков, соединенных телепортом, затем L групп по 3 числа - координаты занятых  отсеков, затем координаты космонавта и координаты отсека,  куда космонавт направляется.  Все данные вводятся через пробел в одну строку.
Программа выводит на экран искомое минимальное количество люков, если космонавт попасть в заданный отсек не сможет, выводит -1.

Пример

Ввод 5 2 6 1 3 3 2 3 2 4 4 4 1 4 3 4 1 1 3 5 4 1 2 4 5 3 2 5 5 5 2 4 1 2 4 2 5 5 4 
Вывод 4


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"