#include<iostream>
using namespace std;
int main()
{
    int num=0;
    int rs[10][30];
    int ps[10];
    cin>>num;
    for(int i=0;i<num;i++)
    {
            int d[30][30];
            for(int j=0;j<30;j++)
            for(int k=0;k<30;k++)
            {
                    d[j][k]=100;
                    d[j][j]=0;
            }
            int m=0,n=0,p=0;
            char x[3],x1[3],x2[3];
            char y[30][3];
            cin>>m>>n>>p;
            ps[i]=p;
            for(int j=0;j<m;j++)
            {
                    cin>>x;
                    y[j][0]=x[0];
                    y[j][1]=x[1];                            
            }
            for(int j=0;j<n;j++)
            {
                    cin>>x2>>x1;
                    int b=-1,c=-1;
                    for(int k=0;k<m;k++)
                    {
                            if(y[k][0]==x2[0]&&y[k][1]==x2[1])
                            {
                                         b=k;
                                         if(c!=-1)          break;
                            }
                            if(y[k][0]==x1[0]&&y[k][1]==x1[1])
                            {
                                          c=k;
                                          if(b!=-1)          break;
                            }
                    }
                    d[b][c]=1;
                    d[c][b]=1;
                    for(int l=0;l<m;l++)
                    {
                            if(d[b][c]+d[c][l]<d[b][l])
                            {
                                      d[b][l]=d[b][c]+d[c][l];
                                      d[l][b]=d[b][l];                           
                            }
                            if(d[c][b]+d[b][l]<d[c][l])
                            {
                                      d[c][l]=d[c][b]+d[b][l];
                                      d[l][c]=d[c][l];                          
                            }        
                    }
            }
            for(int j=0;j<p;j++)
            {
                    int sum=0;
                    cin>>sum>>x>>x1;
                    int b=-1,c=-1;
                    for(int k=0;k<m;k++)
                    {
                            if(y[k][0]==x[0]&&y[k][1]==x[1])
                            {
                                         b=k;
                                         if(c!=-1)          break;
                            }
                            if(y[k][0]==x1[0]&&y[k][1]==x1[1])
                            {
                                          c=k;
                                          if(b!=-1)          break;
                            }
                    }
                    if(d[b][c]==100)      sum=-1;
                    else
                    {
                        sum*=d[b][c];
                        sum*=100;
                    }
                    rs[i][j]=sum;
            }        
    }
	cout<<"SHIPPING ROUTES OUTPUT"<<endl<<endl;
    for(int i=0;i<num;i++)
    {
            cout<<"DATA SET  "<<i+1<<endl<<endl;
            for(int j=0;j<ps[i];j++)
            {
                    if(rs[i][j]==-1)     cout<<"NO SHIPMENT POSSIBLE"<<endl;
                    else                cout<<"$"<<rs[i][j]<<endl;
            }
			cout<<endl;
    }
	cout<<"END OF OUTPUT"<<endl;
    return 1;    
}