eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Город Киото хорошо известен своим китайским планом: его улицы идут либо с Севера на Юг, либо с Востока на Запад. Некоторые улицы пронумерованы, но большинство из них имеют реальные имена. Перекрестки названы по именам улиц, пересекающихся в нем. Например Каварамачи-Сандзе является пересечение улицы Каварамачи и улицы Сандзе. Но возникла проблема: какое имя должно стоять на первом месте? С первого взгляда кажется что это не имеет значения: один говорит Каварамачи-Сандзе (Север-Юг сначала), другой Сандзе-Каварамачи (сначала Восток-Запад). Но с опытом понимаешь, что на самом деле важен "порядок" на улицах. Например, Сидзе является <<сильнее>> Каварамачи, которая в свою очередь <<сильнее>> Сандзе. Этот порядок можно использовать в названиях перекрестков. На вход подается список известных названий перекрестков \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} \InputFile The input is a sequence of data sets, each of the form \begin{verbatim} N\end{verbatim}\begin{verbatim} Crossing1\end{verbatim}\begin{verbatim} ...\end{verbatim}\begin{verbatim} CrossingN\end{verbatim}\begin{verbatim} M\end{verbatim}\begin{verbatim} Question1\end{verbatim}\begin{verbatim} ...\end{verbatim}\begin{verbatim} QuestionM\end{verbatim}Both Crossings and Questions are of the form \textbf{X-Y} where \textbf{X} and \textbf{Y} are strings of alphanumerical characters, of lengths no more than \textbf{16}. There is no white space, and case matters for alphabetical characters. \textbf{N} and \textbf{M} are between \textbf{1} and \textbf{1000} inclusive, and there are no more than \textbf{200} streets in a data set. The last data set is followed by a line containing a zero. \OutputFile The output for each data set should be composed of \textbf{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 \textbf{YES} or \textbf{NO} without any spaces.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #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
Çıxış verilənləri #1
8
YES
NO
YES
NO
YES
NO
4
YES
YES
NO
NO
Mənbə 2004 ACM International Collegiate Programming Contest, Japan Domestic Contest, Ehime, Япония, Июль 2, Задача F