Названия перекрестков
Названия перекрестков
Город Киото хорошо известен своим китайским планом: его улицы идут либо с Севера на Юг, либо с Востока на Запад. Некоторые улицы пронумерованы, но большинство из них имеют реальные имена.
Перекрестки названы по именам улиц, пересекающихся в нем. Например Каварамачи-Сандзе является пересечение улицы Каварамачи и улицы Сандзе. Но возникла проблема: какое имя должно стоять на первом месте? С первого взгляда кажется что это не имеет значения: один говорит Каварамачи-Сандзе (Север-Юг сначала), другой Сандзе-Каварамачи (сначала Восток-Запад). Но с опытом понимаешь, что на самом деле важен "порядок" на улицах. Например, Сидзе является "сильнее" Каварамачи, которая в свою очередь "сильнее" Сандзе. Этот порядок можно использовать в названиях перекрестков.
На вход подается список известных названий перекрестков X-Y. Улицы имеют направление Север-Юг или Восток-Запад, причем пересекаться могут только ортогональные улицы.
Поскольку Ваш список не полный, то Вы захотели его завершить используя следующие правила:
две улицы A и B имеют одинаковую "силу" если выполняются условия (1) - (3):
- они обе пересекают третью улицу C из входных данных;
- не существует такой улицы D что D-A и B-D присутствуют во входных данных;
- не существует такой улицы E что A-E и E-B присутствуют во входных данных;
Будем использовать это определение для расширения отношения "сильный":
- A сильнее B, если существует последовательность A =
A1
,A2
, ...,An
= B, где n как минимум 2 и для любого i в промежутке 1 .. n - 1 либоAi-Ai+1
входной перекресток, либоAi
иAi+1
имеют одинаковую силу.
Вам следует выяснить, являются ли заданные имена перекрестков X-Y допустимыми. Ответить следует утвердительно, если Вы можете вывести допустимость имени, и отрицательно если не можете. А именно:
- YES если можно сделать вывод что две улицы ортогональны, причем X сильнее Y
- NO иначе
Входные данные
Состоит из нескольких тестов в формате
n
Crossing1
...
Crossingn
m
Question1
...
Questionm
Пересечения и Запросы имеют вид
X-Y
где X и Y - строки из букв и цифр длины не больше 16. Строки не содержат пробелы, регистр букв существенен.
n и m между 1 и 1000 включительно, в каждом тесте не более 200 улиц.
Последняя строка содержит ноль.
Выходные данные
Для каждого теста вывести m + 1 строку. В первой строке содержится количество улиц в городе, за которой следуют ответы на вопросы - либо YES, либо NO.
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
8 YES NO YES NO YES NO 4 YES YES NO NO