// CECR 2012
// Problem E: Word Equations
// Correct solution, O(kp)
// Author: Grzegorz Herman
#include <cassert>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int MAXK = 1000;
const int MAXS = 5;
const int MAXT = 5000;
struct eq
{
string s[2];
eq * e[2];
vector<int> b;
eq(string s0="", string s1="")
{
s[0] = s0; s[1] = s1;
e[0] = e[1] = 0;
}
int term(string const & p, int j)
{
int maxi = s[0].length();
int maxj = p.length();
for (int i=0; i<maxi && j<maxj; ++i)
if (s[0][i] == p[j])
++j;
return j;
}
int best(string const & p, int j)
{
//cout << s[0] << " " << s[1] << " " << j << endl;
if (b.empty()) b.resize(p.length()+1, -1);
//if(b[j]>=0) cout << "dp : " << s[0] << " " << s[1] << " " << j << endl;
return b[j] = (b[j]>=0) ? b[j] : e[1] ? e[1]->best(p, e[0]->best(p, j)) : term(p, j);
// return e[1] ? e[1]->best(p, e[0]->best(p, j)) : term(p, j);
}
};
int main()
{
int z; for (cin >> z; z; --z)
{
map<string, eq> M;
string s[3], t, p;
int k; for (cin >> k; k; --k)
{
cin >> s[2] >> s[1] >> s[0];
if (s[0][0]<='Z') cin >> s[1] >> s[1];
M[s[2]] = eq(s[0], s[1]);
}
for (map<string, eq>::iterator i = M.begin(); i != M.end(); ++i)
if (i->second.s[0][0]<='Z')
for (int k=0; k<2; ++k)
i->second.e[k] = &M[i->second.s[k]];
cin >> t >> p;
cout << (M[t].best(p, 0) < p.length() ? "NO" : "YES") << endl;
}
return 0;
}
Ly8gQ0VDUiAyMDEyCi8vIFByb2JsZW0gRTogV29yZCBFcXVhdGlvbnMKLy8gQ29ycmVjdCBzb2x1dGlvbiwgTyhrcCkKLy8gQXV0aG9yOiBHcnplZ29yeiBIZXJtYW4KCiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx2ZWN0b3I+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTUFYSyA9IDEwMDA7CmNvbnN0IGludCBNQVhTID0gNTsKY29uc3QgaW50IE1BWFQgPSA1MDAwOwoKc3RydWN0IGVxCnsKICAgIHN0cmluZyAgICAgIHNbMl07CiAgICBlcSAqICAgICAgICBlWzJdOwogICAgdmVjdG9yPGludD4gYjsKICAgIAogICAgZXEoc3RyaW5nIHMwPSIiLCBzdHJpbmcgczE9IiIpCiAgICB7CiAgICAgICAgc1swXSA9IHMwOyBzWzFdID0gczE7CiAgICAgICAgZVswXSA9IGVbMV0gPSAwOwogICAgfQoKICAgIGludCB0ZXJtKHN0cmluZyBjb25zdCAmIHAsIGludCBqKQogICAgewogICAgICAgIGludCBtYXhpID0gc1swXS5sZW5ndGgoKTsKICAgICAgICBpbnQgbWF4aiA9IHAubGVuZ3RoKCk7CiAgICAgICAgZm9yIChpbnQgaT0wOyBpPG1heGkgJiYgajxtYXhqOyArK2kpCiAgICAgICAgICAgIGlmIChzWzBdW2ldID09IHBbal0pCiAgICAgICAgICAgICAgICArK2o7CiAgICAgICAgcmV0dXJuIGo7CiAgICB9CgogICAgaW50IGJlc3Qoc3RyaW5nIGNvbnN0ICYgcCwgaW50IGopCiAgICB7CiAgICAJLy9jb3V0IDw8IHNbMF0gPDwgIiAiIDw8IHNbMV0gPDwgIiAiIDw8IGogPDwgZW5kbDsKICAgICAgICBpZiAoYi5lbXB0eSgpKSBiLnJlc2l6ZShwLmxlbmd0aCgpKzEsIC0xKTsKICAgICAgICAvL2lmKGJbal0+PTApIGNvdXQgPDwgImRwIDogIiA8PCBzWzBdIDw8ICIgIiA8PCBzWzFdIDw8ICIgIiA8PCBqIDw8IGVuZGw7CiAgICAgICAgcmV0dXJuIGJbal0gPSAoYltqXT49MCkgPyBiW2pdIDogZVsxXSA/IGVbMV0tPmJlc3QocCwgZVswXS0+YmVzdChwLCBqKSkgOiB0ZXJtKHAsIGopOwogICAgICAgLy8gcmV0dXJuIGVbMV0gPyBlWzFdLT5iZXN0KHAsIGVbMF0tPmJlc3QocCwgaikpIDogdGVybShwLCBqKTsKICAgIH0KfTsKCmludCBtYWluKCkKewogICAgaW50IHo7IGZvciAoY2luID4+IHo7IHo7IC0teikKICAgIHsKICAgICAgICBtYXA8c3RyaW5nLCBlcT4gTTsKICAgICAgICBzdHJpbmcgc1szXSwgdCwgcDsKICAgICAgICBpbnQgazsgZm9yIChjaW4gPj4gazsgazsgLS1rKQogICAgICAgIHsKICAgICAgICAgICAgY2luID4+IHNbMl0gPj4gc1sxXSA+PiBzWzBdOwogICAgICAgICAgICBpZiAoc1swXVswXTw9J1onKSBjaW4gPj4gc1sxXSA+PiBzWzFdOwogICAgICAgICAgICBNW3NbMl1dID0gZXEoc1swXSwgc1sxXSk7CiAgICAgICAgfQogICAgICAgIGZvciAobWFwPHN0cmluZywgZXE+OjppdGVyYXRvciBpID0gTS5iZWdpbigpOyBpICE9IE0uZW5kKCk7ICsraSkKICAgICAgICAgICAgaWYgKGktPnNlY29uZC5zWzBdWzBdPD0nWicpCiAgICAgICAgICAgICAgICBmb3IgKGludCBrPTA7IGs8MjsgKytrKQogICAgICAgICAgICAgICAgICAgIGktPnNlY29uZC5lW2tdID0gJk1baS0+c2Vjb25kLnNba11dOwogICAgICAgIGNpbiA+PiB0ID4+IHA7CiAgICAgICAgY291dCA8PCAoTVt0XS5iZXN0KHAsIDApIDwgcC5sZW5ndGgoKSA/ICJOTyIgOiAiWUVTIikgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==