#include <bits/stdtr1c++.h>
using namespace std;
vector<int> vertex[34];
bool seen[34];
int main(){
int numMap; cin >> numMap;
while (numMap--){
int numTrials; cin >> numTrials;
set<string> trials;
while (numTrials--){
string trial; cin>>trial;
trials.insert(trial);
}
int numVertices, numEdges; cin >> numVertices >> numEdges;
for (int i=0; i<numVertices; i++){
vertex[i].clear();
}
for (int i=0; i<numEdges; i++){
int a,b; string c; cin >> a >> b >> c;
if (trials.count(c)) continue;
vertex[a].push_back(b);
vertex[b].push_back(a);
}
memset(seen, 0, sizeof seen);
seen[0]=true;
queue<int> q({0});
while(!q.empty()){
int u = q.front(); q.pop();
for (int v:vertex[u]){
if(!seen[v]){
q.push[v];
seen[v]=true;
}
}
}
cout << seen[numVertices-1] << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkdHIxYysrLmg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjxpbnQ+IHZlcnRleFszNF07CmJvb2wgc2VlblszNF07CgppbnQgbWFpbigpewoJaW50IG51bU1hcDsgY2luID4+IG51bU1hcDsKCXdoaWxlIChudW1NYXAtLSl7CgkJaW50IG51bVRyaWFsczsgY2luID4+IG51bVRyaWFsczsKCQlzZXQ8c3RyaW5nPiB0cmlhbHM7CgkJd2hpbGUgKG51bVRyaWFscy0tKXsKCQkJc3RyaW5nIHRyaWFsOyBjaW4+PnRyaWFsOwoJCQl0cmlhbHMuaW5zZXJ0KHRyaWFsKTsKCQl9CgkJaW50IG51bVZlcnRpY2VzLCBudW1FZGdlczsgY2luID4+IG51bVZlcnRpY2VzID4+IG51bUVkZ2VzOwoJCWZvciAoaW50IGk9MDsgaTxudW1WZXJ0aWNlczsgaSsrKXsKCQkJdmVydGV4W2ldLmNsZWFyKCk7CgkJfQoJCQoJCWZvciAoaW50IGk9MDsgaTxudW1FZGdlczsgaSsrKXsKCQkJaW50IGEsYjsgc3RyaW5nIGM7IGNpbiA+PiBhID4+IGIgPj4gYzsKCQkJaWYgKHRyaWFscy5jb3VudChjKSkgY29udGludWU7CgkJCXZlcnRleFthXS5wdXNoX2JhY2soYik7CgkJCXZlcnRleFtiXS5wdXNoX2JhY2soYSk7CgkJCQoJCX0KCQoJCW1lbXNldChzZWVuLCAwLCBzaXplb2Ygc2Vlbik7CgkJc2VlblswXT10cnVlOwoJCXF1ZXVlPGludD4gcSh7MH0pOwoJCXdoaWxlKCFxLmVtcHR5KCkpewoJCQlpbnQgdSA9IHEuZnJvbnQoKTsgcS5wb3AoKTsKCQkJZm9yIChpbnQgdjp2ZXJ0ZXhbdV0pewoJCQkJaWYoIXNlZW5bdl0pewoJCQkJCXEucHVzaFt2XTsKCQkJCQlzZWVuW3ZdPXRydWU7CgkJCQl9CgkJCX0KCQl9CgkKCQljb3V0IDw8IHNlZW5bbnVtVmVydGljZXMtMV0gPDwgZW5kbDsKCX0JCgkKCQoJcmV0dXJuIDA7CgkKfQ==