1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<queue>

 4 #include<cstring>

 5 #define go(i,a,b) for(int i=a;i<=b;i++)

 6 #define fo(i,a,x) for(int i=a[x];i>-1;i=e[i].next)

 7 #define mem(a,b) memset(a,b,sizeof(a))

 8 #define inf 1000000000

 9 using namespace std;const int N=90000;

10 struct E{int v,next,flow,cap;}e[N*20];

11 char socket[N][30],device[N][2][30],change[N][2][30];

12 int n,m,s,t,head[N],k,K,d[N],preE[N],preN[N],cur[N],num[N];

13 void ADD(int u,int v,int flow,int cap){e[K]=(E){v,head[u],flow,cap};head[u]=K++;}

14 void Big_Riced_Pancake()

15 {//m(device)--->k(change)--->n(socket)

16     go(i,1,m){ADD(s,i,0,1);ADD(i,s,0,0);

17     go(j,1,k)if(!strcmp(device[i][1],change[j][0]))ADD(i,j+m,0,inf),ADD(j+m,i,0,0);

18     go(j,1,n)if(!strcmp(device[i][1],socket[j]))ADD(i,m+k+j,0,1),ADD(m+k+j,i,0,0);}

19     go(i,1,n)ADD(m+k+i,t,0,1),ADD(t,m+k+i,0,0);go(i,1,k){

20     go(j,1,k)if((i!=j)&&(!strcmp(change[i][1],change[j][0])))ADD(i+m,j+m,0,inf),ADD(j+m,i+m,0,0);

21     go(j,1,n)if(!strcmp(change[i][1],socket[j]))ADD(i+m,m+k+j,0,inf),ADD(m+k+j,i+m,0,0);}

22 }

23 void BFS(){queue<int>q;bool vis[N]={0};q.push(t);vis[t]=1;d[t]=0;

24     while(!q.empty()){int u=q.front();q.pop();fo(i,head,u)

25     {int v=e[i].v;if(!vis[v]&&!e[i].cap)vis[v]=1,d[v]=d[u]+1,q.push(v);}}

26 }

27 int aug(){int u,a=inf;

28     u=t;while(u!=s){int i=preE[u];a=min(a,e[i].cap-e[i].flow);u=preN[u];}

29     u=t;while(u!=s){int i=preE[u];e[i].flow+=a;e[i^1].flow-=a;u=preN[u];}return a;

30 }

31 int main(){scanf("%d",&n);go(i,1,n)scanf("%s",socket[i]);

32     scanf("%d",&m);go(i,1,m)go(j,0,1)scanf("%s",device[i][j]);

33     scanf("%d",&k);go(i,1,k)go(j,0,1)scanf("%s",change[i][j]);

34     mem(head,-1);K=0;s=0;t=n+m+k+1;Big_Riced_Pancake();

35     BFS();go(i,0,t)num[d[i]]++,cur[i]=head[i];int u=s,flow=0;

36     while(d[s]<t+1){u==t?flow+=aug(),u=s:1;bool retreat=1;

37         fo(i,cur,u){int v=e[i].v;if(e[i].cap>e[i].flow&&d[u]==d[v]+1)

38         {retreat=0;preN[v]=u;cur[u]=preE[v]=i;u=v;break;}}if(!retreat)continue;

39         int Min=t;

40         fo(i,head,u){int v=e[i].v;if(e[i].cap>e[i].flow)Min=min(Min,d[v]);}

41         if(!(--num[d[u]]))break;num[d[u]=Min+1]++;cur[u]=head[u];if(u!=s)u=preN[u];

42     }printf("%d\n",m-flow);return 0;

43 }//Paul_Guderian