#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+IG51bU1hcDsKCXdoaWxlKG51bU1hcC0tKXsKCQlpbnQgbnVtVHJpYWxzOyBjaW4gPj4gbnVtVHJpYWxzOwoJCXNldDxzdHJpbmc+IHRyaWFsczsKCQl3aGlsZShudW1UcmlhbHMtLSl7CgkJCXN0cmluZyB0cmlhbDsgY2luPj50cmlhbDsKCQkJdHJpYWxzLmluc2VydCh0cmlhbCk7CgkJfQoJCWludCBudW1WZXJ0aWNlcywgbnVtRWRnZXM7IGNpbiA+PiBudW1WZXJ0aWNlcyA+PiBudW1FZGdlczsKCQlmb3IgKGludCBpPTA7IGk8bnVtVmVydGljZXM7IGkrKyl7CgkJCXZlcnRleFtpXS5jbGVhcigpOwoJCX0KCQkKCQlmb3IgKGludCBpPTA7IGk8bnVtRWRnZXM7IGkrKyl7CgkJCWludCBhLGI7IHN0cmluZyBjOyBjaW4gPj4gYSA+PiBiID4+IGM7CgkJCWlmICh0cmlhbHMuY291bnQoYykpIGNvbnRpbnVlOwoJCQl2ZXJ0ZXhbYV0ucHVzaF9iYWNrKGIpOwoJCQl2ZXJ0ZXhbYl0ucHVzaF9iYWNrKGEpOwoJCQkKCQl9CgkKCQltZW1zZXQoc2VlbiwgMCwgc2l6ZW9mIHNlZW4pOwoJCXNlZW5bMF09dHJ1ZTsKCQlxdWV1ZTxpbnQ+IHEoezB9KTsKCQl3aGlsZSghcS5lbXB0eSgpKXsKCQkJaW50IHUgPSBxLmZyb250KCk7IHEucG9wKCk7CgkJCWZvciAoaW50IHY6dmVydGV4W3VdKXsKCQkJCWlmKCFzZWVuW3ZdKXsKCQkJCQlxLnB1c2godik7CgkJCQkJc2Vlblt2XT10cnVlOwoJCQkJfQoJCQl9CgkJfQoJCgkJY291dCA8PCBzZWVuW251bVZlcnRpY2VzLTFdIDw8IGVuZGw7Cgl9CQoJCgkKCXJldHVybiAwOwoJCn0=