ACM International Collegiate Programming Contest
Japan Domestic, 2004-07-02
京都の街並みは唐の都長安をまねて作られており，
通りは東西方向と南北方向に走っている．通りには，
番号の名前が付いているものもあるが，
そうでない名前が付いているものの方が多い．
交差点の名前はそこで交わる通りの名前をつなげたものである．
例えば，「河原町三条」は「河原町通り」と「三条通り」の交差点である．
一見単純な命名規則だが，どちらの通りを先にするかが問題となる．
初めての人にその順番は恣意的に思えるかもしれない．
「河原町三条」は南北の通りが先なのに，「四条河原町」だと東西が先になる．
慣れてくると，実は通りに優先順位のようなものがあることが分かってくる．
例えば，「河原町」は「三条」より強いが，「四条」はさらに強い．
この優先順位を利用して，二つの通りが交わる交差点の名前が推測できる．
この問題では，「Kawaramachi-Sanjo」 のような既知の交差点名のリストが入力として与えられる． 通りには東西と南北しかなく，同じ方向の通りは交わらないものとする．
与えられるリストは一部の交差点しか含まないが， ここからできるだけ多くの強弱の情報を引き出したい． まず，次の規則で，同じくらいの強さの通りについて調べる．
この水準を利用して，より多くの通りの強さが比較できる．
次に，いくつかのX-Y形式の名前について， その名前が交差点の名前として有効かどうかを聞かれる． 有効と判断できる場合は「YES」と， そう判断できない場合は「NO」と答えなさい． 具体的な条件は以下に記す．
入力は以下の形のデータセットが並んでいる
N 交差点1 ... 交差点N M 質問1 ... 質問M
「交差点」と「質問」は，いずれも
X-Y
という形の，ハイフンで区切られた二つの16字以内の英数字の列からなる．
各行に空白は含まれず，大文字と小文字は区別する．
NとMは1以上1000以下の整数で，一つのデータセットに現れる通りの数は200以下である．
最後のデータセットの後に0とだけ書かれた1行がある．
各データセットに対して，M+1行を出力する． 1行目は「交差点」部に現れる通りの数を書く． 2行目以降は各「質問」の答えを，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
ここに1番目のデータがある．
The ACM ICPC