// Arup Guha
// 3/9/2020
// Solution to 2020 UCF HS Contest Problem: Colorful Neighborhood

import java.util.*;

public class colorful {
	
	final public static int NO_HOUSE = -2;
	final public static int NO_DIST = -1;
	
    public static ArrayList[] g;
    public static int n;
    public static char[] colors;

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);
        int nC = stdin.nextInt();

		// Process each case.
        for (int loop=1; loop<=nC; loop++) {

			// Read in the basic characteristics.
            n = stdin.nextInt();
            int e = stdin.nextInt();
            int numQ = stdin.nextInt();
            colors = stdin.next().toCharArray();
			
			// Form the graph.
            g = new ArrayList[n];
            for (int i=0; i<n; i++)
                g[i] = new ArrayList<Integer>();
            for (int i=0; i<e; i++) {
                int v1 = stdin.nextInt()-1;
                int v2 = stdin.nextInt()-1;
                g[v1].add(v2);
                g[v2].add(v1);
            }

			// We will run a modified Dijkstra's 26 times, once for each letter.
            int[][] dist = new int[26][n];
			int[][] house = new int[26][n];
			
            for (int i=0;i<26; i++) {

				// Initially we can't get anywhere.
                Arrays.fill(dist[i], NO_DIST);
				Arrays.fill(house[i], NO_HOUSE);
                
				// All the distances from all letters i is 0, we use these as our
				// simultaneous starting points.
                LinkedList<Integer> q = new LinkedList<Integer>();
                for (int j=0; j<n; j++) {
                    if (colors[j]-'A' == i) {
                        dist[i][j] = 0;
						house[i][j] = j;
                        q.offer(j);
                    }
                }

				// This is the usual BFS loop.
                while (q.size() > 0) {
					
					// This is the next vertex.
                    int cur = q.poll();
					
					// See where we can go from cur.
                    for (Integer x: (ArrayList<Integer>)g[cur] ) {
						
						// Update distance and which house we came from.
                        if (dist[i][x] == NO_DIST) {
                            dist[i][x] = dist[i][cur]+1;
                            house[i][x] = house[i][cur];
                            q.offer(x);
                        }
						
						// This is another house we can come from with the same distance.
						else if (dist[i][x] == dist[i][cur]+1) {
							house[i][x] = Math.min(house[i][x], house[i][cur]);
						}
                    }
                }

            }

			// Case header
            System.out.println("Neighborhood #"+loop+":");

			// Process each query.
            for (int i=0; i<numQ; i++) {
				
				// Get the query.
                int v = stdin.nextInt()-1;
                int col = stdin.next().charAt(0) - 'A';

				// They want the house number to go to.
                System.out.println(house[col][v]+1);
            }
            System.out.println();
            
        }
    }
}