eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Удовольствие в Бикольском регионе

Удовольствие в Бикольском регионе

Бикольский регион (Регион \textbf{5}) состоит из шести провинций. Это Албай, Северный Камаринес, Южный Камаринес, Сорсогон и острова-провинции Катандуанес и Масбате. В Бикольском регионе расположены города Ирига, Легаспи, Лигао, Масбате, Нага, Сорсогон и Табако. \includegraphics{https://static.e-olymp.com/content/1a/1a8535855594de709d491ccbb29171e526813eff.jpg} \textit{\textbf{Рисунок 1}}: Карта Бикольского региона (местоположения приведены только для иллюстрации) Многие участники не смогли дождаться завершения соревнования, и начали планировать исследование региона. Они начали расспрашивать где находятся определенные города и начали записывать их относительные местоположения. \InputFile Входные данные состоят из нескольких тестов. Каждый тест содержит два множества данных. Первое множество описывает относительное расположение первого города ко второму, а второе множество содержит запросы на относительное положение первого города относительно второго. Например Множество данных 1 Множество данных 2 В приведенном выше примере имеется \textbf{5 }и \textbf{4} записи во множествах данных \textbf{1} и \textbf{2} соответственно. Множество данных \textbf{1 }состоит из пар городов и их относительного положения. Каждая запись указывает на относительное положение места \textbf{1} к \textbf{2}. Например, запись (Naga City, City of Iriga, Northwest) означает, что город Нага расположен на северо-запад от города Ирига. Множество данных не содержат обратного отношения. Например (City of Iriga, Naga City, Southeast). Входные данные начинаются двумя целыми числами \textbf{m} и \textbf{n}, задающих количество записей во множестве данных \textbf{1} и \textbf{2} соответственно, причем (\textbf{1 }≤ \textbf{m }≤ \textbf{100}) и (\textbf{1 }≤ \textbf{n }≤ \textbf{50}). Далее следует \textbf{m} записей описания местоположений и\textbf{n }записей запросов. Данные в записях разделены запятыми и могут содержать смешанные случаи. Возможными относительными положениями являются Север, Юг, Восток, Запад, Северо-Восток, Северо-Запад, Юго-Восток и Юго-Запад. Считается, что каждое относительное положение задает расстояние \textbf{1}. То есть \textbf{1 }на\textbf{ }север, \textbf{1 }на юг, \textbf{1} на восток, \textbf{1 }на запад, \textbf{1 }на север и \textbf{1 }на\textbf{ }восток, \textbf{1} на север и \textbf{1} на запад, \textbf{1} на юг и \textbf{1} на восток, \textbf{1 }на юг и \textbf{1 }на запад соответственно. То есть расстояние от Масбате до Нага такое же как и от Сорсогон до Легаспи. Между тестами находится пустая строка. За последним тестом следует одно число ноль. \OutputFile Для каждого теста выведите относительное местоположение заданных в запросах городов. Вывести "\textbf{Relative location cannot be determined}", если информации для выполнения запроса недостаточно; хотя программа сама должна постараться получить всю необходимую информацию для выполнения запроса.
Лимит времени 5 секунд
Лимит использования памяти 128 MiB
Входные данные #1
5 4
Naga City,City of Iriga,Northwest
Masbate City,Naga City,Southeast
Tabaco City,City of Ligao,Northeast
Sorsogon City,Legazpi City,Southeast
City of Ligao,Legazpi City,West
Naga City,City of Iriga
City of Iriga, Naga City
Sorsogon City, Naga City
Sorsogon City, City of Ligao

0
Выходные данные #1
Case 1
Naga City is northwest of City of Iriga
City of Iriga is southeast of Naga City
Relative location cannot be determined
Sorsogon City is southeast of City of Ligao
Источник ACM ICM Philippines Multi-Provincial Programming Contest 2013