#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>

char path1[200];
char path2[200];
int path[200];
bool hover[200];
int route[200];
int bestr[200];
float best;
int bestd;

bool find(int d, int dmax, float l, char a, bool h, char g, int n)
{
  int i;
  float l2;
  bool found=false;
  bool found2;
  
  if (a==g)
    {
      if (h) l+=7.0;
      if (l<best)
	{
	  best=l;
	  for (i=0; i<=d; i++)
	    bestr[i]=route[i];
	  bestd=d;
	}
      return true;
    }
  if (d==dmax) return false;
  for (i=0; i<n; i++)
    {
      if (path1[i]==a)
	{
	  route[d]=i;
	  l2=l+((float)(path[i]))/(hover[i] ? 9.0 : 5.0);
	  if (h!=hover[i]) l2+=7.0;
	  found2=find(d+1, dmax, l2, path2[i], hover[i], g, n);
	  found=found2||found;
	}
    }
  return found;
}

void main()
{
  int d, m, n, p, i, j, k,l;
  char a,b,c;
  
  cin>>d;
  for(i=1; i<=d; i++)
    {
      cout<<"Data set "<<i<<":\n\r";
      cin>>m>>n>>p;
      for (j=0; j<n; j++)
	{
	  cin>>path1[j]>>path2[j]>>path[j]>>c;
	  hover[j]=(c=='H');
	  n++;j++;
	  path1[j]=path2[j-1];
	  path2[j]=path1[j-1];
	  path[j]=path[j-1];
	  hover[j]=hover[j-1];
	  if (hover[j])
	    {
	      n++; j++;
	      hover[j]=false;
	      path1[j]=path1[j-1];
	      path2[j]=path2[j-1];
	      path[j]=path[j-1];
	      n++;j++;
	      hover[j]=false;
	      path1[j]=path2[j-1];
	      path2[j]=path1[j-1];
	      path[j]=path[j-1];
	    }
	}
      for (j=1; j<=p; j++)
	{
	  cout<<"Route "<<j<<":\n\r";
	  cin>>a>>b;
	  k=10;
	  best=1000000.0;
	  while (!find(0,k,0,a,false,b,n))
	    {
	      k+=5;
	    }
	  find(0,k+2,0,a,false,b,n);
	  for (l=0; l<bestd; l++)
	    {
	      cout<<"  "<<path1[bestr[l]]<<" "<<path2[bestr[l]]<<" ";
	      if (hover[bestr[l]])
		cout<<"riding\n\r";
	      else cout<<"walking\n\r";
	    }
	  cout<<"Total time ";
	  printf("%.1f seconds\n\r", best);
	}
    }
}