Name the Crossing

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

Name the Crossing

京都の街並みは唐の都長安をまねて作られており, 通りは東西方向と南北方向に走っている.通りには, 番号の名前が付いているものもあるが, そうでない名前が付いているものの方が多い.
交差点の名前はそこで交わる通りの名前をつなげたものである. 例えば,「河原町三条」は「河原町通り」と「三条通り」の交差点である. 一見単純な命名規則だが,どちらの通りを先にするかが問題となる. 初めての人にその順番は恣意的に思えるかもしれない. 「河原町三条」は南北の通りが先なのに,「四条河原町」だと東西が先になる. 慣れてくると,実は通りに優先順位のようなものがあることが分かってくる. 例えば,「河原町」は「三条」より強いが,「四条」はさらに強い. この優先順位を利用して,二つの通りが交わる交差点の名前が推測できる.

この問題では,「Kawaramachi-Sanjo」 のような既知の交差点名のリストが入力として与えられる. 通りには東西と南北しかなく,同じ方向の通りは交わらないものとする.

与えられるリストは一部の交差点しか含まないが, ここからできるだけ多くの強弱の情報を引き出したい. まず,次の規則で,同じくらいの強さの通りについて調べる.

  • 以下の(1)〜(3)すべてが成り立つならば,通りAとBが「同水準である」とい う.
    1. A,B両方との交差点が入力の中にあるような通りCがある.
    2. D-AとB-Dが入力の中にあるような通りDはない.
    3. A-EとE-Bが入力の中にあるような通りEはない.

この水準を利用して,より多くの通りの強さが比較できる.

  • 長さ2以上の通りの列A=A1, A2, ..., An=B があり,1からn-1までの任意のiについて Ai-Ai+1が入力の交差点であるか, または AiとAi+1が同水準であれば, 「Aの水準がB以上である」という.

次に,いくつかのX-Y形式の名前について, その名前が交差点の名前として有効かどうかを聞かれる. 有効と判断できる場合は「YES」と, そう判断できない場合は「NO」と答えなさい. 具体的な条件は以下に記す.

  • YES XとYの方向が異なり,Xの水準がY以上であると判断できるとき
  • NO それ以外の場合

Input

入力は以下の形のデータセットが並んでいる

N
交差点1
...
交差点N
M
質問1
...
質問M

「交差点」と「質問」は,いずれも

X-Y

という形の,ハイフンで区切られた二つの16字以内の英数字の列からなる. 各行に空白は含まれず,大文字と小文字は区別する.
NMは1以上1000以下の整数で,一つのデータセットに現れる通りの数は200以下である.

最後のデータセットの後に0とだけ書かれた1行がある.

Output

各データセットに対して,M+1行を出力する. 1行目は「交差点」部に現れる通りの数を書く. 2行目以降は各「質問」の答えを,YESかNOで表す.

Sample Input

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

Output for the Sample Input

8
YES
NO
YES
NO
YES
NO
4
YES
YES
NO
NO

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Ehime, Japan, 2004
http://www.ehime-u.ac.jp/ICPC/