There is an ancient saying that "All Roads Lead to Rome". If this were true, then there is a simple algorithm for nding a path between any two cities. To go from city A to city B, a traveller could take a road from A to Rome, then from Rome to B. Of course, a shorter route may exist.

The network of roads in the Roman Empire had a simple structure: beginning at Rome, a number of roads extended to the nearby cities. From these cities, more roads extended to the next further cities, and so on. Thus, the cities could be thought of as existing in levels around Rome, with cities in the ith level only connected to cities in the i - 1th and i + 1th levels (Rome was considered to be at level 0). No loops existed in the road network. Any city in level i was connected to a single city in level i - 1, but was connected to zero or more cities in level i + 1. Thus, to get to Rome from a given city in level i, a traveller could simply walk along the single road leading to the connected i - 1 level city, and repeat this process, with each step getting closer to Rome.

Given a network of roads and cities, your task is to find the shortest route between any two given cities, where distance is measured in the number of intervening cities.

Input
The first line is the number of test cases, followed by a blank line.

The first line of each test case of the input contains two numbers in decimal notation separated byva single space. The first number (m) is the number of roads in the road network to be considered. The second number (n) represents the number of queries to follow later in the file.

For each test case, in the next m lines in the input each contain the names of a pair of cities separated by a single space. A city name consists of one or more letters, the first of which is in uppercase. No two cities begin with the same letter. The name Rome always appears at least once in this section of input, for each test case; this city is considered to be at level 0, the lowest-numbered level. The pairs of names indicate that a road connects the two named cities. The first city named on a line exists in a
lower level than the second named city. The road structure obeys the rules described above. For each test case, no two lines of input in this section are repeated.

The next n lines, for each test case in the input each contain the names of a pair of cities separated by a single space. City names are as described above. These pairs of cities are the query pairs. Your task for each query pair is to find the shortest route from the first named city to the second. Each of the cities in a query pair is guaranteed to have appeared somewhere in the previous input section, for each test case, describing the road structure.
Each test case will be separated by a single line.

Output
In each test case, for each of the n query pairs, output a sequence of uppercase letters indicating the shortest route between the two query pair cities. The sequence must be output as consecutive letters, without intervening whitespace, on a single line. For each test case, the first output line corresponds to the first query pair, the second output line corresponds to the second query pair, and so on. The letters in each sequence indicate the first letter of the cities on the desired route between the query pair cities, including the query pair cities themselves. A city will never be paired with itself in a query.
Print a blank line between the outputs for two consecutive test cases.

Sample Input
1

7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa

Sample Output
TRP
MTRPF
AVTG

#include<stdio.h>
#include<stdlib.h>
#define N 20
typedef int element;
struct cell { 
	element data; 
	int priority;
	struct cell *next; 
};
 

typedef  struct { 
	struct cell *front; 
} queue;


queue CreateQueue()
{
	queue q;
	q.front = NULL;
	return q;
}

int isEmptyQueue(queue q)
{
	return q.front == NULL;
}

int EnQueue(queue *q, element e, int priority)
{
	struct cell *temp, *href;
	temp = (struct cell *) malloc(sizeof(struct cell));
	if (!temp) return 0;
	temp->data = e;
	temp->priority = priority;
	if (q->front == NULL || priority < q->front->priority) {/*Queue is empty or item to be added has priority more than first item*/
		temp->next = q->front;
		q->front = temp;
	}
	else
	{
		href = q->front;
		while (href->next != NULL && href->next->priority <= priority)
			href = href->next;
		temp->next = href->next;
		href->next = temp;
	}

	return 1;
}

int DeQueue(queue *q)
{
	struct cell *temp;
	if (isEmptyQueue(*q)) return 0;
	temp = q->front;
	q->front = q->front->next;
	free(temp);
	return 1;
}

int Front(queue q, element *e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.front->data;
	return 1;
}

 

void display_queue(queue tmp)
{
	struct cell *temp = tmp.front;

	if (temp == NULL)
		printf("Queue is empty\n");
	else
	{
		printf("Queue is :\n");
		printf("Item\n");
		while (temp != NULL)
		{
			printf("%5d         %5d\n\n", temp->priority, temp->data);
			temp = temp->next;
		}
	}
}
void delete_head(struct cell **nodeRef)
{
	struct cell *p;
	p = *nodeRef;
	*nodeRef = (*nodeRef)->next;
	free(p);
}

// delete a given element (recursive)
int delete_value(struct cell **nodeRef, element e)
{
	if (*nodeRef == NULL)
		return 0;
	if ((*nodeRef)->data == e)
	{
		delete_head(nodeRef);
		return 1;
	}
	return delete_value(&((*nodeRef)->next), e);
}


void recursive_ordered_insert(struct cell **node, element value, int priority)
{
	struct cell *temp;
	if ((*node == NULL) || !((*node)->priority < priority))
	{
		temp = *node;
		*node = (struct cell *) malloc(sizeof(struct cell));
		if (!*node) return ;
		(*node)->data = value;
		(*node)->priority = priority;
		(*node)->next = temp;
		return;
	}

	 recursive_ordered_insert(&((*node)->next), value, priority);

}


void update_priority(queue *q, element data, int priority) {
	if (delete_value(&(q->front), data) == 1)
		recursive_ordered_insert(&(q->front), data, priority);
}

 

 

 
void printPath(int Path[], int t)
{
    if(Path[t]!=t)
        printPath(Path, Path[t]);
    printf("%c",t+'A');
}

 

 

int main()
{
    int T;
    int m, n , i, dist, v, w;
    int distance[26], Path[26];
    char str1[255], str2[255];
    queue q;
    int adjList[26][26]; 
    
    
    scanf("%d", &T);
    while ( T-- )
    {
        scanf("%d %d", &m, &n);
  
        for (v = 0; v < 26; ++v)
            for (w = 0; w < 26; ++w)
                adjList[v][w]=0;

        for (i = 0; i < m; ++i)
        {
            scanf("%s %s", str1, str2);
            adjList[str1[0]-'A'][str2[0]-'A']=1;
            adjList[str2[0]-'A'][str1[0]-'A']=1;
        }

        for (i = 0; i < n; ++i)
        {
            scanf("%s %s", str1, str2);
             
            q = CreateQueue();
            for (w = 0; w < 26; ++w)
            {
                distance[w] = -1;
                Path[w]=w;
            }
	        
	        EnQueue(&q, str1[0]-'A',0);
	        distance[str1[0]-'A'] = 0;
	        while (Front(q, &v)) {
		        DeQueue(&q);
		        for (w = 0; w < 26; w++) 
			        if (adjList[v][w]) {
				        dist = distance[v]+ adjList[v][w];
				        if (distance[w] == -1) {
					        distance[w] = dist;
					        EnQueue(&q, w, dist);
					        Path[w] = v;
				        }
				        else
					        if (distance[w] > dist) {
					        	distance[w] = dist;
						        update_priority(&q, w, dist);
						        Path[w] = v;
					        }

			        }
	        }

            printPath(Path, str2[0]-'A' );
            printf("\n");
        }
        if (T)
           printf("\n");
    }
	return 0;
}