1556: 距离查询
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：12
Solved：11
Description
约翰有N个农场，标记1~N。有M条垂直和水平的道路连接农场，每条道路的长度各不相同。每个农场都可以直接连接到北部（N）、南部（S）、东部（E）或西部（W）最多4个其他农场。农场位于道路的终点，正好有一条道路连接一对农场，没有两条道路交叉。他希望知道两个农场之间的道路长度，农场的地图如下图所示。“1 6 13 E ”表示从F1到F6有一条长度为13的道路，F6在F1的东部。
Input
第1行包含两个正整数N（2<=N<=40000）和M（1<=M<=40000）。第2..M+1行，每行包含4个字符a,b,l,d,表示两个农场a和b由一条路相连，长度为l（1<=l<=1000）,d是字符“N”、“S”、“E”或“W”，表示从a到b的道路方向。第M+2行，包含单个整数K（1<=K<=10000）,表示查询个数。接下来的K行，每行都包含距离查询的两个农场的编号。
Output
对于每个查询，都单行输出两个农场的距离。
Sample Input Copy
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 4
2 6Sample Output Copy
13
3
36