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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Город Киото хорошо известен своим китайским планом: его улицы идут либо с Севера на Юг, либо с Востока на Запад. Некоторые улицы пронумерованы, но большинство из них имеют реальные имена.

Перекрестки названы по именам улиц, пересекающихся в нем. Например Каварамачи-Сандзе является пересечение улицы Каварамачи и улицы Сандзе. Но возникла проблема: какое имя должно стоять на первом месте? С первого взгляда кажется что это не имеет значения: один говорит Каварамачи-Сандзе (Север-Юг сначала), другой Сандзе-Каварамачи (сначала Восток-Запад). Но с опытом понимаешь, что на самом деле важен "порядок" на улицах. Например, Сидзе является «сильнее» Каварамачи, которая в свою очередь «сильнее» Сандзе. Этот порядок можно использовать в названиях перекрестков.

На вход подается список известных названий перекрестков X-Y. Улицы имеют направление Север-Юг или Восток-Запад, причем пересекаться могут только ортогональные улицы.

Поскольку Ваш список не полный, то Вы захотели его завершить используя следующие правила:

  • две улицы A и B имеют одинаковую "силу" если выполняются условия (1) - (3):

  1. они обе пересекают третью улицу C из входных данных

  2. не существует такой улицы D что D-A и B-D присутствуют во входных данных

  3. не существует такой улицы 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ə

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