/*
分析:
2012亚洲杭州站H题。
水题-、-,字典树+松弛,暴力过了。用了字典树,不过据
说更暴力的、不用字典树的,也能ac-、-III
2011-11-08
*/
#include"stdio.h" #include"string.h" #include"stdlib.h" #include"queue" using namespace std; #define N 1011 #define M 10011 int n; int dis[N]; struct Eage { int from,to; int next; }eage[2*M]; int tot,head[N]; void add(int a,int b) { eage[tot].from=a; eage[tot].to=b; eage[tot].next=head[a]; head[a]=tot++; } struct dictree { struct dictree *child[52]; int flag; }; struct dictree *root; void insert(char str[],int k) { struct dictree *now,*next; int i,l,temp; now=root; for(i=0;str[i];i++) { if(str[i]>='a') temp=str[i]-'a'; else temp=str[i]-'A'+26; if(now->child[temp]!=NULL) now=now->child[temp]; else { next=(struct dictree *)malloc(sizeof(struct dictree)); for(l=0;l<52;l++) next->child[l]=NULL; next->flag=-1; now->child[temp]=next; now=next; } } now->flag=k; } int find(char str[]) { struct dictree *now; int i,temp; now=root; for(i=0;str[i];i++) { if(str[i]>='a') temp=str[i]-'a'; else temp=str[i]-'A'+26; if(now->child[temp]!=NULL) now=now->child[temp]; else return -1; } return now->flag; } void build() { int m; int i,l; char str[111],str2[111]; int f1,f2; root=(struct dictree *)malloc(sizeof(struct dictree)); for(l=0;l<52;l++) root->child[l]=NULL; root->flag=-1; for(i=0;i<n;i++) {scanf("%s",str);insert(str,i);} tot=0; memset(head,-1,sizeof(head)); scanf("%d",&m); while(m--) { scanf("%s%s",str,str2); f1=find(str); f2=find(str2); add(f1,f2); add(f2,f1); } } void getdis(int s) { queue<int>q; int hash[N]; int j,v; int now,next; memset(dis,-1,sizeof(dis)); memset(hash,0,sizeof(hash)); dis[s]=0; hash[s]=1; q.push(s); while(!q.empty()) { now=q.front(); q.pop(); for(j=head[now];j!=-1;j=eage[j].next) { v=eage[j].to; if(hash[v]) continue; hash[v]=1; next=v; dis[next]=dis[now]+1; q.push(next); } } } void solve() { int i,l; int ans=0; for(i=0;i<n;i++) { getdis(i); for(l=0;l<n;l++) { if(dis[l]==-1) {ans=-1;break;} ans=ans>dis[l]?ans:dis[l]; } if(ans==-1) break; } printf("%d\n",ans); } int main() { while(scanf("%d",&n),n) { build(); solve(); } return 0; }