Названия перекрестков
Названия перекрестков
Город Киото хорошо известен своим китайским планом: его улицы идут либо с Севера на Юг, либо с Востока на Запад. Некоторые улицы пронумерованы, но большинство из них имеют реальные имена.
Перекрестки названы по именам улиц, пересекающихся в нем. Например Каварамачи-Сандзе является пересечение улицы Каварамачи и улицы Сандзе. Но возникла проблема: какое имя должно стоять на первом месте? С первого взгляда кажется что это не имеет значения: один говорит Каварамачи-Сандзе (Север-Юг сначала), другой Сандзе-Каварамачи (сначала Восток-Запад). Но с опытом понимаешь, что на самом деле важен "порядок" на улицах. Например, Сидзе является «сильнее» Каварамачи, которая в свою очередь «сильнее» Сандзе. Этот порядок можно использовать в названиях перекрестков.
На вход подается список известных названий перекрестков X-Y. Улицы имеют направление Север-Юг или Восток-Запад, причем пересекаться могут только ортогональные улицы.
Поскольку Ваш список не полный, то Вы захотели его завершить используя следующие правила:
две улицы A и B имеют одинаковую "силу" если выполняются условия (1) - (3):
они обе пересекают третью улицу C из входных данных
не существует такой улицы D что D-A и B-D присутствуют во входных данных
не существует такой улицы 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 иначе
Giriş verilənləri
The input is a sequence of data sets, each of the form
N
Crossing1
...
CrossingN
M
Question1
...
QuestionM
Both Crossings and Questions are of the form
X-Y
where X and Y are strings of alphanumerical characters, of lengths no more than 16. There is no white space, and case matters for alphabetical characters.
N and M are between 1 and 1000 inclusive, and there are no more than 200 streets in a data set.
The last data set is followed by a line containing a zero.
Çıxış verilənləri
The output for each data set should be composed of M+1 lines, the first one containing the number of streets in the Crossing part of the input, followed by the answers to each question, either YES or NO without any spaces.
Nümunə
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