[Usaco2004 Feb]Navigation Nightmare 导航噩梦
时间限制：10s 空间限制：128MB
题目描述
农夫约翰有N(2≤N≤40000)个农场，标号1到N,M(2≤M≤40000)条的不同的垂直或水
平的道路连结着农场，道路的长度不超过1000.这些农场的分布就像下面的地图一样，
图中农场用F1..F7表示, 每个农场最多能在东西南北四个方向连结4个不同的农场．此外，农场只处在道路的两端．道路不会交叉且每对农场间有且仅有一条路径．邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复了．每一条道路的信息如下：
从农场23往南经距离10到达农场17
从农场1往东经距离7到达农场17
当约翰重新获得这些数据时，他有时被的鲍伯的问题打断：“农场1到农场23的曼哈顿距离是多少？”所谓在(XI，Yi)和(X2，y2)之间的“曼哈顿距离”，就是lxl - X21+lyl - y21．如果已经有足够的信息，约翰就会回答这样的问题（在上例中答案是17），否则他会诚恳地抱歉并回答-1.
输入格式
第1行：两个分开的整数N和M.
第2到M+1行：每行包括4个分开的内容，F1，F2，三，D分别描述两个农场的编号，道路的长度，F1到F2的方向N，E，S，w．
第M+2行：一个整数，K(1≤K≤10000)，表示问题个数．
第M+3到M+K+2行：每行表示一个问题，由3部分组成：Fi，F2，，．其中Fi和F2表示两个被问及的农场．而/(1≤J≤M)表示问题提出的时刻．J为1时，表示得知信息1但未得知信息2时．
输出格式
第1到K行：每行一个整数，回答问题．表示两个农场间的曼哈顿距离．不得而知则输出-1.
样例输入
7 6 1 6 13 E 6 3 9 E 3 5 7 S 4 1 3 N 2 4 20 W 4 7 2 S 3 1 6 1 1 4 3 2 6 6
样例输出
13 -1 10
提示
在时刻1，约翰知道1到6的距离为13;在时刻3，1到4的距离仍然不知道；在时刻6，位置6向
北3个距离，向西7个距离于位置2，所以距离为10.
题目来源
Green