// by Dan Joyce
// solves Problem 7: Shipping Routes 
// of 1996 Mid Atlantic programming contest

// input describes a network of warehouses 
// output gives cost of shipping between certain pairs of warehouses 

import java.io.*;
import common.doinput; 

// create linked list by declaring a class that contains objects
// of itself

class whouse {

  String name = "  ";
  whouse link;

  };

/********************************************************************/

class problem7 {

  /* linked list stuff starts here ... using adjacency list  ***********/

  static whouse warehouses [];   // adjacency list represents the graph
  static int M;                         // number of warehouses

  static int find (String searchname) {
  // returns where in linked list searchname occurs
  // -1 if searchname is not on the list
  
  int place = -1;
 
  for (int i = 0; i <= (M-1); i++)
   if (warehouses[i].name.equals(searchname))
      place = i;

  return place;
  };

  /* end of linked list stuff *****************************************/


  public static void main (String [] args) throws IOException {

    String in_string;       // input string
    int numsets;            // number of data sets
    int N;                  // number of shipping legs
    int P;                  // number of shipping requests
    String name1, name2;    // names of ends of a shipping leg
    int index;              // index of a warehouse in adj list  
    int distances[];        // number of legs from the source
    int size;               // size of shipping request
    int sourcewh, destwh;   // index of src and dest of shipment
    int searchind, foundind;// used while updating distances
    int cost;               // calculated cost
 
    doinput myinput = new doinput();

    whouse temp_wh;
    String temp_s; 

    System.out.println ("SHIPPING ROUTES OUTPUT");

    numsets = myinput.nextint();

    for (int count = 1; count <= numsets; count++)
      {
      System.out.println("DATA SET " + count);
      System.out.println();

      M = myinput.nextint();
      N = myinput.nextint();
      P = myinput.nextint();

      /* create warehouse adjacency list header and get names */
      warehouses = new whouse[M];
      for (int i = 1; i <= M; i++)
        {
        whouse temp = new whouse();
        temp.name = myinput.nextsubstring();
        warehouses[i-1] = temp;
        }

      /* read the shipping legs and set links to reflect them */
      for (int i = 1; i <= N; i++)
        {
        name1 = myinput.nextsubstring();
        name2 = myinput.nextsubstring();

        index = find(name1);
        temp_wh = new whouse();
        temp_s = new String(name2);
        temp_wh.link = warehouses[index].link;        
        temp_wh.name = temp_s;
        warehouses[index].link = temp_wh;

        index = find(name2);
        temp_wh = new whouse();
        temp_s = new String(name1);
        temp_wh.link = warehouses[index].link;        
        temp_wh.name = temp_s;
        warehouses[index].link = temp_wh;
        }

      /* read the shipping requests and determine distance and cost */
      for (int shipreqnum = 1; shipreqnum <= P; shipreqnum++)
        {
        /* read shipping request info */
        size = myinput.nextint();
        name1 = myinput.nextsubstring();
        name2 = myinput.nextsubstring();  
        sourcewh = find(name1);
        destwh = find(name2);
       
        /* create and initialize distance array */
        distances = new int[M];
        for (int i = 0; i < M; i++) distances[i] = M + 1;
        distances[sourcewh] = 0;

        for (int searchlevel = 0; searchlevel < M; searchlevel++)
          {
          for (searchind = 0; searchind < M; searchind++)
            {
            if (distances[searchind] == searchlevel)
              {
              /* go thru connected legs and change em if appropriate */
              temp_wh = warehouses[searchind].link;
              while (temp_wh != null)
                {
                foundind = find(temp_wh.name);
                if (distances[foundind] == M+1)
                   distances[foundind] = searchlevel + 1;
                temp_wh = temp_wh.link;
                }
              }
            }
          };

        /* output results */
        if (distances[destwh] == ( M + 1 ))
          System.out.println("NO SHIPMENT POSSIBLE");
        else {cost = size * 100 * distances[destwh];
              System.out.println("$" + cost);
             }
        };
      System.out.println ();
      };

    System.out.println ("END OF OUTPUT");
  }
}