/*
 *   Robert M. Baldwin
 *   
 *   If you use this code, please leave a comment at
 *   http://www.veganbob.com/ or send me an email at
 *   bob@veganbob.com
 *   
 *   Thank you, and enjoy!
 *   
 */

import java.io.*;
import java.lang.*;
import java.util.*;
import java.math.*;

class nextdoor
{
	public static void main(String[] args) throws Exception
	{
		(new nextdoor()).go();
	}
	public void prnln(String txt)
	{
		System.out.println(txt);
	}
	public void prn(String txt)
	{
		System.out.print(txt);
	}
	public void err(String txt)
	{
		//System.out.println("> " + txt);
	}

	
	String ans;
	int[][] path;
	int[][] grid;
	ArrayList<String> routers;
	ArrayList<String> rconnections;
	ArrayList<String> computers;
	ArrayList<String> comprouter;
	int INF = 500;

	public void go() throws Exception
	{
		Scanner in = new Scanner(new File("nextdoor.in"));
		int cases = in.nextInt();
		err(""+cases);
		for(int x=0; x<cases; x++)
		{
			int r = in.nextInt(), c = in.nextInt(), t = in.nextInt();
			//err("R: "+r+" C: "+c+" T: "+t);
			in.nextLine();
			String cur;
			String curarray[];
			routers = new ArrayList<String>();
			rconnections = new ArrayList<String>();
			computers = new ArrayList<String>();
			comprouter = new ArrayList<String>();
			
			// read routers
			for(int y=0; y<r; y++)
			{
				cur = in.nextLine();
				rconnections.add(cur);
				err("cur Rs: "+cur);
				curarray = cur.split(" ");
				if(!routers.contains(curarray[0]))
					routers.add(curarray[0]);
				if(!routers.contains(curarray[1]))
					routers.add(curarray[1]);
			}

			grid = new int[routers.size()][routers.size()];
			path = new int[routers.size()][routers.size()];
			for(int y=0; y<routers.size(); y++)
				for(int z=0; z<routers.size(); z++)
				{
					grid[y][z] = (y==z)? 0 : INF;
					path[y][z] = (y==z||path[y][z]==INF)? -1 : y;
				}

			for(int y=0; y<rconnections.size(); y++)
			{
				err(""+rconnections.size());
				curarray = rconnections.get(y).split(" ");
				grid[routers.indexOf(curarray[0])][routers.indexOf(curarray[1])] = 1;
				grid[routers.indexOf(curarray[1])][routers.indexOf(curarray[0])] = 1;
			}

			// Floyd-Warshall's
			for(int k=0; k<routers.size(); k++)
				for(int i=0; i<routers.size(); i++)
					for(int j=0; j<routers.size(); j++)
					{
						if(grid[i][j]>grid[i][k]+grid[k][j])
						{
							grid[i][j]=grid[i][k]+grid[k][j];
							path[i][j]=path[k][j];
						}
					}

			// read computers
			for(int y=0; y<c; y++)
			{
				cur = in.nextLine();
				curarray = cur.split(" ");
				computers.add(curarray[0]);
				comprouter.add(curarray[1]);
			}

			// do test cases
			prnln("Data set #"+(x+1)+":");
			for(int y=0; y<t; y++)
			{
				cur = in.nextLine();
				curarray = cur.split(" ");
				ans = comprouter.get(computers.indexOf(curarray[0]));
				int count = 1 + printpath(routers.indexOf(comprouter.get(computers.indexOf(curarray[0]))),
					routers.indexOf(comprouter.get(computers.indexOf(curarray[1]))));
				prnln(""+curarray[0]+" to "+curarray[1]+" requires "+count+" hops: "+ans);
			}
			prnln("");

		}

	}

	public int printpath(int from, int to)
	{
		int count = 0;
		if(path[from][to]!=from && from!=to)
			count = printpath(from, path[from][to]) + printsubpath(path[from][to], to);
		else if(from!=to)
		{
			ans += " "+routers.get(to);
			count++;
		}
		return count;
	}

	public int printsubpath(int from, int to)
	{
		int count = 0;
		if(path[from][to]!=from && from!=to)
			count = printpath(from, path[from][to]) + printpath(path[from][to], to);
		if(from!=to)
		{
			ans += " "+routers.get(to);
			count++;
		}
		return count;
	}
}