#P1983. Name the Crossing
Name the Crossing
描述
京都市以其中国式规划而闻名:街道要么是南北走向,要么是东西走向。有些街道有编号,但大多数有真实名称。十字路口以交叉的两条街的名字命名,例如,河原町三条是河原町街与三条街的交叉口。但有一个问题:哪个名字应该在前面?起初顺序似乎相当任意:人们说河原町三条(南北优先),但四条河原町(东西优先)。通过一些经验,人们意识到其实在街道上似乎存在一种“顺序”,例如在上述例子中,四条比河原町“强”,而河原町又比三条“强”。人们可以利用这一顺序推断出其他交叉口的名称。您得到的输入是已知交叉口名称列表X-Y。街道要么是南北走向,要么是东西走向,并且只有正交街道可以交叉。由于您的列表非常不完整,您可以开始使用以下规则来补充它:
◾如果两条街道A和B具有相等的强度,则以下条件(1)到(3)都为真:
1.它们都在输入中交叉同一条第三街道C。
2.不存在街道D,使得D-A和B-D出现在输入中。
3.不存在街道E,使得A-E和E-B出现在输入中。
我们使用这个定义来扩展我们的强度关系:
◾当存在一个序列A = A1, A2, ..., An = B,其中n至少为2,
并且对于任意的i在1到n-1之间,或者Ai-Ai+1是一个输入交叉,或者Ai和Ai+1具有相等的强度时,A就比B强。
然后你会被问到某些其他可能的交叉名称X-Y是否有效。如果你能推断出名称的有效性,你应该肯定回答,如果不能则否定。具体来说:
◾如果你可以推断出这两条街道是正交的,并且X比Y强,则回答YES。 否则回答NO。
输入
输入是一个数据集的序列,每个数据集的形式为: N
Crossing1
...
CrossingN
M
Question1
...
QuestionM
交叉口和问题均为形式为
X-Y
其中X和Y是长度不超过16的字母数字字符的字符串。没有空格,字母字符的大小写敏感。
N和M的范围在1到1000之间(含),并且一个数据集中最多有200条街道。
最后一个数据集后面跟着一个包含零的行。
输出
每个数据集的输出应由M 1行组成,第一行包含输入中交叉部分的街道数量,后面是每个问题的答案,答案为YES或NO,之间不留空格。
样例输入
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
来源
日本2004国内赛