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.
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