//Notes: 


#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <map>
#include <list>
#include <iterator>
#include <string>


////////////////////////////////////////////////////////////////////



// Graph structure is based upon std::map:
//  typedef ... Node;
//     typedef map<Node, map<Node, Numeric> > graph;
//  Each source node is mapped to a structure that in turn maps
//  each destination node reachable from that source to a numeric
//  distance.
//  e.g., graph g;
//        g[node1][node2] = 0;


using namespace std;


typedef std::string Node;
typedef map<Node, map<Node, double> > Graph;
typedef double Distance;
typedef list<Node> Path;

//template <class Node, class Graph, class Distance, class Path>
class Dijkstra {

// Computes shortest paths from the start node to the finish node.
// If no path between them exists, return an empty path. If a path is found,
// total distance of path is returned in totalDistance.
// Graph:
//    Graph structure is based upon std::map:
//     typedef ... Node;
//     typedef map<Node, map<Node, Numeric> > graph;
//    Each source node is mapped to a structure that in turn maps
//    each destination node reachable from that source to a numeric
//    distance.
//    e.g., Graph g;
//          g[node1][node2] = 0;
//
// Node: some type that can be used as the key in a map
// Distance: a numeric type
// Path: a container of Nodes supporting clear and insert operations
//



class Edge {
public:
  Edge () : distance(0) {}
  Edge (Distance ds, Node src, Node dt)
    : distance(ds), source(src), destination(dt)  {}


  bool operator < (const Edge& right) const
    { return distance < right.distance; }

  bool operator > (const Edge& right) const
    { return distance > right.distance; }

  Distance distance;
  Node source;
  Node destination;
};
 

  Graph& g;
  
public:

  Dijkstra (Graph& theGraph): g(theGraph)  {}

  // Find the shortest path between two nodes, returning the total
  // distance
  Distance solve (Node start, Node finish, Path& path );
};



////////////////////////////////////////////////////////////////////




bool debugging = false;



// typedef  map<string, map<string, float> > Graph;


struct RoadSegment {
  string road;
  string fromCity;
  string toCity;
  double distance;
  double time;
};


void readRoad (istream& in, list<RoadSegment>& roads)
{
  string line;
  getline(in, line);
  istringstream lineIn (line);

  string roadName;
  string city1, city2;
  double dist, time;
  lineIn >> roadName >> city1;

  while (lineIn >> dist >> time >> city2)
    {
      RoadSegment seg;
      seg.road = roadName;
      seg.fromCity = city1;
      seg.toCity = city2;
      seg.distance = dist;
      seg.time = time;

      if (debugging)
	cerr << "read " << roadName << " " << city1 << " "
	     << dist << " " << time
	     << city2 << endl;
      roads.push_back (seg);
      city1 = city2;
    }
}


void buildDistanceGraph (Graph& g,
			 list<RoadSegment>& roads,
			 list<string>& cities)
{
  for (list<RoadSegment>::iterator r = roads.begin();
       r != roads.end(); ++r)
    {
      string roadName = string(" ")
	+ r->road + " " + r->fromCity + " " + r->toCity;
      g[r->fromCity][roadName] = 0.0;
      g[roadName][r->toCity] = r->distance;
      g[r->toCity][roadName] = 0.0;
      g[roadName][r->fromCity] = r->distance;
    }
}


void buildTimeGraph (Graph& g,
		     list<RoadSegment>& roads,
		     list<string>& cities)
{
  for (list<RoadSegment>::iterator r = roads.begin();
       r != roads.end(); ++r)
    {
      string roadName = string(" ")
	+ r->road + " " + r->fromCity + " " + r->toCity;
      g[r->fromCity][roadName] = 0.0;
      g[roadName][r->toCity] = r->time;
      g[r->toCity][roadName] = 0.0;
      g[roadName][r->fromCity] = r->time;
    }
}


void buildTurnsGraph (Graph& g,
		      list<RoadSegment>& roads,
		      list<string>& cities)
{
  for (list<RoadSegment>::iterator r = roads.begin();
       r != roads.end(); ++r)
    {
      string roadName = string(" ") + r->road + " ";
      g[r->fromCity][roadName] = 0.0;
      g[roadName][r->toCity] = 1.0;
      g[r->toCity][roadName] = 0.0;
      g[roadName][r->fromCity] = 1.0;
    }
}



void query(Graph& g, string city1, string city2)
{
  Dijkstra/*<string, Graph, double, list<string> > */ minPath(g);
  list<string> solution;
  double distance = minPath.solve (city1, city2, solution);

  cout << "from " << city1 << endl;

  string lastRoad;
  string lastCity;

  for (list<string>::iterator i = solution.begin();
       i != solution.end(); ++i)
    {
      string at = *i;
      if (at[0] == ' ')
	{
	  // This is a road segment
	  string road = at.substr(1);
	  road = road.substr(0, road.find(' '));
	  
	  if (lastRoad != "" && road != lastRoad)
	    cout << lastRoad << " to " << lastCity << endl;

	  lastRoad = road;
	}
      else
	lastCity = at;
    }
  cout << lastRoad << " to " << lastCity << endl;
}






void mapquest (istream& in)
{
  int nCities;
  in >> nCities;
  list<string> cityNames;
  for (int i = 0; i < nCities; ++i)
    {
      string name;
      in >> name;
      cityNames.push_back(name);
    }

  int nRoads;
  in >> nRoads;
  string dummy;
  getline(in, dummy);

  list<RoadSegment> roads;
  for (int r = 0; r < nRoads; ++r)
    {
      readRoad(in, roads);
    }


  Graph distanceGraph, timeGraph, turnsGraph;

  buildDistanceGraph (distanceGraph, roads, cityNames);
  buildTimeGraph (timeGraph, roads, cityNames);
  buildTurnsGraph (turnsGraph, roads, cityNames);


  string queryType, city1, city2;
  while (in >> queryType)
    {
      in >> city1 >> city2;
      if (queryType == "time")
	query(timeGraph, city1, city2);
      else if (queryType == "distance")
	query(distanceGraph, city1, city2);
      else if (queryType == "turns")
	query(turnsGraph, city1, city2);
    }
}


int main (int argc, char** argv)
{
  if (argc == 1)
    mapquest (cin);
  else
    { // For debugging purposes allo file name to be supplies on the command
      // line (CygWin insight debugger does not work well with
      // redirected input)
      debugging = 1;
      ifstream in (argv[1]);
      mapquest(in);
    }
  return 0;
}



///////////////////////////////////////////////////////////////

// Dijkstra's algorithm
//  From Budd, Data Structures in C++ using the Standard Template Library
//   with modifications by S Zeil, Old Dominion University

#include <queue>
#include <vector>


using namespace std;


Distance Dijkstra::solve (Node start, Node finish, Path& path )
{
  map<Node, Distance> distances;
  map<Node, Node> cameFrom;
  
  priority_queue<Edge, vector<Edge>, greater<Edge> > que;
  que.push(Edge(0, start, start));
  
  while (!que.empty()) {
    // pull nearest node from queue
    Distance distance = que.top().distance;
    Node dest = que.top().destination;
    Node source = que.top().source;
    que.pop();
    
    // If we haven't seen it already, process it
    if (distances.count(dest) == 0) {
      // add it to the shortest distance map
      distances[dest] = distance;
      cameFrom[dest] = source;
      // and put values into the queue
      map<Node, Distance>::iterator gstart, gstop;
      gstart = g[dest].begin();
      gstop = g[dest].end();
      for (; gstart != gstop; ++gstart) {
	Node successorNode = (*gstart).first;
	Distance successorDistance  = (*gstart).second;
	que.push(Edge(distance+successorDistance,
		      dest, successorNode));
      }
    }
  }
  
  list<Node> tempPath;
  Distance totalDistance = (Distance)(0);
  
  if (cameFrom.count(finish) > 0) {
    Node n = finish;
    tempPath.push_front(n);
    while (n != start) {
      n = cameFrom[n];
      tempPath.push_front(n);
    }
    totalDistance = distances[finish];
  }
  path.clear();
  copy (tempPath.begin(), tempPath.end(), back_inserter<Path>(path));
  return totalDistance;
}