#include<bits/stdc++.h>

using namespace std;

bool color[32];

int cost[32];

vector<int>graph[32];

map<string,int>mp;

string source,dest;

void bfs()
{
    int i,j;

    queue<int>Q;

    Q.push(mp[source]);

    color[mp[source]] = true;

    cost[mp[source]] = 0;

    while(!Q.empty())
    {
        i = Q.front();

        Q.pop();

        int sz = graph[i].size();

        for(j=0; j<sz; j++)
        {
            int u = graph[i][j];

            if(!color[u])
            {
                color[u] = true;

                cost[u] = cost[i]+1;

                Q.push(u);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int test,x,warehouse,legs,query,i,key,request;

    string input,s,d;

    cin>>test;

    cout<<"SHIPPING ROUTES OUTPUT\n\n";

    for(x=1; x<=test; x++)
    {
        cout<<"DATA SET  "<<x<<"\n\n";

        cin>>warehouse>>legs>>query;

        for(i=1; i<=warehouse; i++)
        {
            cin>>input;
        }

        key = 0;

        for(i=1; i<=legs; i++)
        {
            cin>>s>>d;

            if(mp.find(s)==mp.end())
            {
                mp[s] = ++key;
            }

            if(mp.find(d)==mp.end())
            {
                mp[d] = ++key;
            }

            graph[mp[s]].push_back(mp[d]);

            graph[mp[d]].push_back(mp[s]);
        }

        for(i=1; i<=query; i++)
        {
            cin>>request>>source>>dest;

            bfs();

            if(cost[mp[dest]]!=0)
            {
                cout<<"$"<<request*cost[mp[dest]]*100<<"\n";
            }
            else
            {
                cout<<"NO SHIPMENT POSSIBLE"<<"\n";
            }

            memset(cost,0,sizeof(cost));

            memset(color,false,sizeof(color));
        }

        cout<<"\n";

        mp.clear();

        for(i=0; i<=warehouse; i++)
        {
            graph[i].clear();
        }
    }

    cout<<"END OF OUTPUT\n";

    return 0;
}