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

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

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

Город Киото хорошо известен своим китайским планом: его улицы идут либо с Севера на Юг, либо с Востока на Запад. Некоторые улицы пронумерованы, но большинство из них имеют реальные имена. Перекрестки названы по именам улиц, пересекающихся в нем. Например Каварамачи-Сандзе является пересечение улицы Каварамачи и улицы Сандзе. Но возникла проблема: какое имя должно стоять на первом месте? С первого взгляда кажется что это не имеет значения: один говорит Каварамачи-Сандзе (Север-Юг сначала), другой Сандзе-Каварамачи (сначала Восток-Запад). Но с опытом понимаешь, что на самом деле важен "порядок" на улицах. Например, Сидзе является <<сильнее>> Каварамачи, которая в свою очередь <<сильнее>> Сандзе. Этот порядок можно использовать в названиях перекрестков. На вход подается список известных названий перекрестков \textbf{X-Y}. Улицы имеют направление Север-Юг или Восток-Запад, причем пересекаться могут только ортогональные улицы. Поскольку Ваш список не полный, то Вы захотели его завершить используя следующие правила: \begin{itemize} \item две улицы \textbf{A }и \textbf{B} имеют одинаковую "силу" если выполняются условия (\textbf{1}) - (\textbf{3}): \end{itemize} \begin{enumerate} \item они обе пересекают третью улицу \textbf{C} из входных данных \item не существует такой улицы \textbf{D} что \textbf{D-A} и \textbf{B-D} присутствуют во входных данных \item не существует такой улицы \textbf{E} что \textbf{A-E} и \textbf{E-B} присутствуют во входных данных \end{enumerate} Будем использовать это определение для расширения отношения "сильный": \begin{itemize} \item \textbf{A} сильнее \textbf{B}, если существует последовательность \textbf{A} = \textbf{A_1, A_2, ..., A_n} = \textbf{B}, где \textbf{n} как минимум \textbf{2} и для любого \textbf{i }в промежутке \textbf{1..n-1} либо \textbf{A_i-A_i_\{+1\}} входной перекресток, либо \textbf{A_i} и \textbf{A_i_\{+1\}} имеют одинаковую силу. \end{itemize} Вам следует выяснить, являются ли заданные имена перекрестков \textbf{X-Y} допустимыми. Ответить следует утвердительно, если Вы можете вывести допустимость имени, и отрицательно если не можете. А именно: \begin{itemize} \item \textbf{YES} если можно сделать вывод что две улицы ортогональны, причем \textbf{X} сильнее \textbf{Y} \item \textbf{NO} иначе \end{itemize} \begin{verbatim} Input 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. Output 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. Sample Input Sample Output 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 \end{verbatim}
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #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