#include<stdio.h>#include<string.h>#define inf 0x3fffffffint n,m,k,map[60][60];int st,ed;int main(){int i,j,x,y,t,op=1,p,w;char s[50][3],ch1[3],ch2[3];scanf("%d",&t);printf("SHIPPING ROUTES OUTPUTnn");while(t--){scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++){map[i][i]=0;for(j=i+1;j<=n;j++)map[i][j]=map[j][i]=inf;}for(i=1;i<=n;i++)scanf("%s",s[i]);for(i=0;i<m;i++){scanf("%s%s",ch1,ch2);for(j=1;j<=n;j++){if(strcmp(ch1,s[j])==0)x=j;if(strcmp(ch2,s[j])==0)y=j;}map[x][y]=map[y][x]=1;}for(p=1;p<=n;p++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(map[i][j]>map[i][p]+map[p][j])map[i][j]=map[i][p]+map[p][j]; printf("DATA SET %dnn",op++);while(k--){scanf("%d%s%s",&w,ch1,ch2);for(i=1;i<=n;i++){if(strcmp(ch1,s[i])==0)x=i;if(strcmp(ch2,s[i])==0)y=i;}if(map[x][y]<inf)printf("$%dn",map[x][y]*w*100);else printf("NO SHIPMENT POSSIBLEn");}printf("n");}printf("END OF OUTPUTn");return 0;}
