1 #include <iostream>
   2 #include <sstream>
   3 #include <string>
   4 #include <algorithm>
   5 #include <vector>
   6 #include <map>
   7 #include <queue>
   8 using namespace std;
   9 
  10 #define GI ({int _t; scanf("%d", &_t); _t;})
  11 #define FOR(i, a, b) for (int i=a; i<b; i++)
  12 #define REP(i, a) FOR(i, 0, a)
  13 template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
  14 int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
  15 #define DBGV(_v) { REP(_i, _v.size()) { cout << _v[_i] << "\t";} cout << endl;}
  16 
  17 int main() {
  18 	int cnt = GI;
  19 	printf("SHIPPING ROUTES OUTPUT\n\n");
  20 	REP(i, cnt) {
  21 		printf("DATA SET  %d\n\n", i+1);
  22 		map<string, int> lookup;
  23 		int nodes = GI, edges = GI, kases = GI;
  24 		int node_cnt = 0;
  25 		REP(j, nodes) {
  26 			string t;
  27 			cin >> t;
  28 			lookup[t] = node_cnt;
  29 			node_cnt++;
  30 		}
  31 		vector <int> t(nodes, 0);
  32 		vector < vector <int> > grid(nodes, t);
  33 		REP(j, edges) {
  34 			string v1, v2;
  35 			cin >> v1 >> v2;
  36 			grid[lookup[v1]][lookup[v2]] = grid[lookup[v2]][lookup[v1]] = 1;
  37 		}
  38 		REP(j, kases) {
  39 			//Do a BFS for each case here...
  40 			queue <int> q;
  41 			vector <bool> visited(nodes, false);
  42 			vector <int> distance(nodes, 0);
  43 			int cost;
  44 			string start, end;
  45 			cin >> cost >> start >> end;
  46 			q.push(lookup[start]);
  47 			visited[lookup[start]] = true;
  48 			distance[lookup[start]] = 0;
  49 			bool found = false;
  50 			while (!q.empty()) {
  51 				int cur = q.front();
  52 				q.pop();
  53 				if (cur == lookup[end]) {
  54 					found = true;
  55 					printf("$%d\n", distance[cur]*cost*100);
  56 					break;
  57 				}
  58 				REP(k, nodes) {
  59 					if (grid[cur][k] == 1 && visited[k] == false) {
  60 						visited[k] = true;
  61 						distance[k] = distance[cur] + 1;
  62 						q.push(k);
  63 					}
  64 				}
  65 			}
  66 			if (found == false) {
  67 				printf("NO SHIPMENT POSSIBLE\n");
  68 			}
  69 		}
  70 		printf("\n");
  71 	}
  72 	printf("END OF OUTPUT\n");
  73 	return 0;
  74 }