#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int MX = 2147483647;

int toInt(char *a){
	return (a[0]-'A')*26+a[1]-'A';
}

int main(){
	printf("SHIPPING ROUTES OUTPUT\n\n");
	int n;
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		printf("DATA SET %d\n\n", i);
		int N,M,P;
		scanf("%d%d%d",&N,&M,&P);
		int adjNum[33] = {0};
		int adj[33][33];
		int dNum = 0;
		int idx[676] = {0};
		for(int j = 0; j < N; j++){
			char tmp[4];
			scanf("%s",tmp);
			int ix = toInt(tmp);
			dNum++;
			idx[ix] = dNum;
		}
		for(int j = 0; j < M; j++){
			char t1[4], t2[4];
			scanf("%s%s",t1,t2);
			int i1 = idx[toInt(t1)], i2 = idx[toInt(t2)];
			adj[i1][adjNum[i1]] = i2;
			adjNum[i1]++;
			adj[i2][adjNum[i2]] = i1;
			adjNum[i2]++;
		}
		for(int j = 0; j < P; j++){
			int lg; char s[4], t[4];
			scanf("%d%s%s",&lg,s,t);
			int is = idx[toInt(s)], it = idx[toInt(t)];
			int dist[33];
			for(int i = 1; i <= N; i++) dist[i] = MX;
			queue<int> bfs;
			dist[is] = 0;
			bfs.push(is);
			while(!bfs.empty()){
				int cur = bfs.front();
				bfs.pop();
				for(int k = 0; k < adjNum[cur]; k++){
					int x = adj[cur][k];
					if(dist[x] == MX){
						dist[x] = dist[cur]+1;
						if(x == it) goto done;
						bfs.push(x);
					}
				}
			}
			done:
			if(dist[it] == MX) printf("NO SHIPMENT POSSIBLE\n");
			else printf("$%d\n", dist[it]*lg*100);
		}
		printf("\n");
	}
	printf("END OF OUTPUT\n");
	return 0;
}