UVa 10009 - All Roads Lead Where?

// UVa 10009 - All Roads Lead Where?

#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
using namespace std;

string path[26];
char p[26];
int k;
bool lnk[26][26];

void build_paths(char c) {
	p[k++] = c;
	path[c] = "";
	for (int kk = 0; kk < k; kk++)
		path[c] = path[c].append(1, p[kk] + 'A');
	for (char d = 0; d < 26; d++)
		if (lnk[c][d]) {
			build_paths(d);
		}
	k--;
}

int main() {
	int t;
	for (cin >> t; t; t--) {
		int m, n;
		cin >> m >> n;
		memset(lnk, false, sizeof(lnk));
		for (int i = 0; i < m; i++) {
			string c1, c2;
			cin >> c1 >> c2;
			lnk[c1[0] - 'A'][c2[0] - 'A'] = true;
		}

		k = 0;
		build_paths('R' - 'A');

		for (int i = 0; i < n; i++) {
			string c1, c2;
			cin >> c1 >> c2;
			string p1 = path[c1[0] - 'A'];
			string p2 = path[c2[0] - 'A'];
			int j = 0;
			while (p1[j] == p2[j]) {
				j++;
				if (j == p1.length() || j == p2.length())
					break;
			}
			for (int k = p1.length() - 1; k >= j; k--)
				printf("%c", p1[k]);
			printf("%c", p1[j - 1]);
			for (int k = j; k < p2.length(); k++)
				printf("%c", p2[k]);
			printf("\n");
		}
		if (t > 1)
			cout << endl;
	}
	return 0;
}