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

Названия перекрестков

Названия перекрестков

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Город Киото хорошо известен своим китайским планом: его улицы идут либо с Севера на Юг, либо с Востока на Запад. Некоторые улицы пронумерованы, но большинство из них имеют реальные имена.

Перекрестки названы по именам улиц, пересекающихся в нем. Например Каварамачи-Сандзе является пересечение улицы Каварамачи и улицы Сандзе. Но возникла проблема: какое имя должно стоять на первом месте? С первого взгляда кажется что это не имеет значения: один говорит Каварамачи-Сандзе (Север-Юг сначала), другой Сандзе-Каварамачи (сначала Восток-Запад). Но с опытом понимаешь, что на самом деле важен "порядок" на улицах. Например, Сидзе является "сильнее" Каварамачи, которая в свою очередь "сильнее" Сандзе. Этот порядок можно использовать в названиях перекрестков.

На вход подается список известных названий перекрестков X-Y. Улицы имеют направление Север-Юг или Восток-Запад, причем пересекаться могут только ортогональные улицы.

Поскольку Ваш список не полный, то Вы захотели его завершить используя следующие правила:

две улицы A и B имеют одинаковую "силу" если выполняются условия (1) - (3):

  1. они обе пересекают третью улицу C из входных данных;

  2. не существует такой улицы D что D-A и B-D присутствуют во входных данных;

  3. не существует такой улицы E что A-E и E-B присутствуют во входных данных;

Будем использовать это определение для расширения отношения "сильный":

  • A сильнее B, если существует последовательность A = A[1], A[2], ..., A[n] = B, где n как минимум 2 и для любого i в промежутке 1 .. n - 1 либо A[i]-A[i+1] входной перекресток, либо A[i] и A[i+1] имеют одинаковую силу.

Вам следует выяснить, являются ли заданные имена перекрестков X-Y допустимыми. Ответить следует утвердительно, если Вы можете вывести допустимость имени, и отрицательно если не можете. А именно:

  • YES если можно сделать вывод что две улицы ортогональны, причем X сильнее Y

  • NO иначе

Входные данные

Состоит из нескольких тестов в формате

n

Crossing[1]

...

Crossing[n]

m

Question[1]

...

Question[m]

Пересечения и Запросы имеют вид

X-Y

где X и Y - строки из букв и цифр длины не больше 16. Строки не содержат пробелы, регистр букв существенен.

n и m между 1 и 1000 включительно, в каждом тесте не более 200 улиц.

Последняя строка содержит ноль.

Выходные данные

Для каждого теста вывести m + 1 строку. В первой строке содержится количество улиц в городе, за которой следуют ответы на вопросы - либо YES, либо NO.

Пример

Входные данные #1
7
Shijo-Kawaramachi
Karasuma-Imadegawa
Kawaramachi-Imadegawa
Nishioji-Shijo
Karasuma-Gojo
Torimaru-Rokujo
Rokujo-Karasuma
6
Shijo-Karasuma
Imadegawa-Nishioji
Nishioji-Gojo
Shijo-Torimaru
Torimaru-Gojo
Shijo-Kawabata
4
1jo-Midosuji
Midosuji-2jo
2jo-Omotesando
Omotesando-1jo
4
Midosuji-1jo
1jo-Midosuji
Midosuji-Omotesando
1jo-1jo
0
Выходные данные #1
8
YES
NO
YES
NO
YES
NO
4
YES
YES
NO
NO
Источник 2004 ACM International Collegiate Programming Contest, Japan Domestic Contest, Ehime, Япония, Июль 2, Задача F