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

Задоволення у Бікольському регіоні

Задоволення у Бікольському регіоні

Ліміт часу 5 секунд
Ліміт використання пам'яті 128 MiB

Бікольський регіон (Регіон 5) складається з шести провінцій. Це Албай, Північний Камаринес, Південний Камаринес, Сорсогон та острови-провінції Катандуанес та Масбате. У Бікольському регіоні розміщені міста Іріга, Легаспі, Лігао, Масбате, Нага, Сорсогон та Табако.

Рисунок 1: Карта Бікольського регіону (місцезнаходження наведені лише для ілюстрації)

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

Вхідні дані

Вхідні дані складаються з декількох тестів. Кожен тест містить дві множини даних. Перша множина описує відносне розміщення першого міста до другого, а друга множина містить запити про відносне положення першого міста відносно другого. Наприклад

Множина даних 1

Множина даних 2

У наведеному вище прикладі є 5 і4 записи у множинах даних 1 та 2 відповідно.

Множина даних 1 складається з пар міст та їх відносного положення. Кажен запис вказує на відносне положення города 1 до 2. Наприклад, запис (Naga City, City of Iriga, Northwest) означає, що місто Нага розміщено на північний захід від міста Іріга. Множини даних не містять зворотного відношення. Наприклад (City of Iriga, Naga City, Southeast).

Вхідні дані починаються двома цілими числами m та n, які задають кількість записів у множинах даних 1 та 2 відповідно, причому (1 m 100) та (1 n 50). Далі йде m записів опису місцезнаходження та n записів запитів.

Дані у записах відокремлено комами і можуть містити змішані випадки. Можливими відносними положеннями є Північ, Південь, Схід, Захід, Північний Схід, Північний Захід, Південний Схід та Південний Захід. Вважається, що кожне відносне положення задає відстань 1. Тобто 1 на північ, 1 на південь, 1 на схід, 1 на захід, 1 на північ та 1 насхід, 1 на північ і 1 на захід, 1 на південь і 1 на схід, 1 на південь і 1 на захід відповідно. Тобто відстань від от Масбате до Нага така ж як і від Сорсогон до Легаспі.

Між тестами знаходиться порожній рядок. За останнім тестом йде одне число нуль.

Вихідні дані

Для кожного тесту виведіть відносне місцезнаходження заданих у запитах міст. Вивести "Relative location cannot be determined", якщо інформації для виконання запиту недостатньо; хоча програма сама повинна постаратись отримати усю необхідну інформацію для виконання запиту.

Приклад

Вхідні дані #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