1 #include<cstdio>  2 #include<cstring>  3 #include<cmath>  4 #include<iostream>  5 #include<algorithm>  6 #include<set>  7 #include<map>  8 #include<stack>  9 #include<vector> 10 #include<queue> 11 #include<string> 12 #include<sstream> 13 #define MAXN 405 14 #define MAXM 805 15 #define INF ((1<<30)/2) 16 #define eps 0.000001 17 #define ALL(x) x.begin(),x.end() 18 #define INS(x) inserter(x,x.begin()) 19 using namespace std; 20 int i,j,k,n,m,x,y,T,num,w; 21  22 const int inf = 0x3f3f3f3f; 23 struct edgenode 24 { 25     int from,to,next; 26     int cap; 27 }edge[MAXM]; 28 int Edge,head[MAXN],ps[MAXN],dep[MAXN]; 29  30 void add_edge(int x,int y,int c) 31 { 32     edge[Edge].from=x; 33     edge[Edge].to=y; 34     edge[Edge].cap=c; 35     edge[Edge].next=head[x]; 36     head[x]=Edge++; 37      38     edge[Edge].from=y; 39     edge[Edge].to=x; 40     edge[Edge].cap=0; 41     edge[Edge].next=head[y]; 42     head[y]=Edge++; 43 } 44  45 int dinic(int n,int s,int t) 46 { 47     int tr,res=0; 48     int i,j,k,l,r,top; 49     while(1){ 50         memset(dep,-1,(n+1)*sizeof(int)); 51         for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS部分，将给定图分层  52         { 53             for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next) 54             { 55                 if (edge[j].cap&&-1==dep[k=edge[j].to]) 56                 { 57                     dep[k]=dep[i]+1;ps[r++]=k; 58                     if(k==t) 59                     { 60                         l=r; 61                         break; 62                     } 63                 } 64             } 65         } 66         if(dep[t]==-1)break; 67          68         for(i=s,top=0;;)//DFS部分  69         { 70             if(i==t)//当前点就是汇点时  71             { 72                 for(k=0,tr=inf;k<top;++k) 73                     if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap; 74                      75                 for(k=0;k<top;++k) 76                     edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr; 77                      78                 res+=tr; 79                 i=edge[ps[top=l]].from; 80             } 81              82             for(j=head[i];j!=-1;j=edge[j].next)//找当前点所指向的点  83                 if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break; 84                  85             if(j!=-1) 86             { 87                 ps[top++]=j;//当前点有所指向的点，把这个点加入栈中  88                 i=edge[j].to; 89             } 90             else 91             {  92                 if (!top) break;//当前点没有指向的点，回溯  93                 dep[i]=-1; 94                 i=edge[ps[--top]].from; 95             } 96         } 97     } 98     return res; 99 }100 101 int main()102 {103     int T,cas,m,t,n,maxflow,i;104     int x,y,c;105     double ans;106     scanf("%d",&T);107     map <string,int> rec;108     string s,s2;109     while(T--)110     {   111         memset(head,-1,sizeof(head));112         Edge=0;113         scanf("%d",&n);114         rec.clear();115         num=1;//设定，0为源点，1为汇点 116         for (i=1;i<=n;i++)117         {118             cin>>s;119             if (!rec.count(s)) rec[s]=++num; 120             add_edge(rec[s],1,1);121         }122         scanf("%d",&m);123         for (i=1;i<=m;i++)124         {125             cin>>s>>s2;126             if (!rec.count(s2)) rec[s2]=++num; 127             add_edge(0,rec[s2],1);128         }129         scanf("%d",&k);130         for (i=1;i<=k;i++)131         {132             cin>>s>>s2;133             if (!rec.count(s))134             {135                 rec[s]=++num;136             }137             if (!rec.count(s2))138             {139                 rec[s2]=++num;140             }141             add_edge(rec[s],rec[s2],INF);142         }143         maxflow=dinic(num,0,1);144         printf("%d\n",m-maxflow); 145         if (T!=0) printf("\n");146     }147     return 0;148 }