#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N,M;
    int x,y;
    string A[800];
    int score[800]={0};
    char dna[20][20];

    cin >> N >> M;


    for(int i=0; i<M; i++) {
        string a;
        cin >> a;

        bool iscontain=false;
        int conv=0;
        int convj=0;
        for( int j=0; j<i; j++)
            if(A[j].find(a)!=string::npos) {
                iscontain=true;
                if(score[j]>conv) {
                    conv=score[j];
                    convj=j;
                }
                break;
            }
        if(iscontain!=true) {
            A[i]=a;
            score[i]++; 
        } else {
            score[convj]++;
            A[i]="";
        }
    }

    bool convine=true;

    while(convine) {
        convine=false;
        for(int i=0; i<M; i++) {
            if(A[i].size()>2){
                string b=A[i].substr(A[i].size()-2);
                for(int j=0; j<M; j++) {
                    if( i==j ) continue;
                    if( A[j][0]==b[0] && A[j][1]==b[1] ){
                        if( A[i].size()+A[j].size()-2 <= N) {
                            A[i] = A[i] + A[j].substr(2);
                            A[j] ="";
                            score[i]+=score[j];
                            score[j]=0;
                            convine=true;
                            break;
                        }
                    }
                }
            }
        }
    }

    convine=true;

    while(convine) {
        convine=false;
        for(int i=0; i<M; i++) {
            if(A[i].size()>2 && A[i].size()<N){
                for(int j=0; j<M; j++) {
                    if( i==j ) continue;
                    if( (A[j].size() > 2) && ((A[i].size()+A[j].size()) <= N) ){
                        A[i] = A[i] + A[j];
                        A[j] ="";
                        score[i]+=score[j];
                        score[j]=0;
                        convine=true;
                        break;
                    }
                }
            }
        }
    }

    for(int i=0; i<M; i++){
        int max=score[i];
        int maxj=i;
        for(int j=i; j<M; j++){
            if(score[j]>max) {
                max=score[j];
                maxj=j;
            }
        }
        if( i!=maxj){
            string tmp;
            tmp=A[maxj];
            A[maxj]=A[i];
            A[i]=tmp;
            int ti=score[maxj];
            score[maxj]=score[i];
            score[i]=ti;
        }
    }

    for(int i=0; i<N; i++) {
        if(A[i].size() < 20) A[i]+="....................";
    }

    for(int i=0; i<N; i++) {
        cout << A[i].substr(0,20) << endl;
    }
};

#include <iostream>
#include <cmath>
#include <vector>
int main(void)
{
  size_t N, M;
  std::cin >> N >> M;
  
  std::vector<int> A(M);
  std::vector<int> B(M);
  for (size_t i = 0; i < M; i++) {
    std::cin >> A[i] >> B[i];
  }

  size_t K;
  std::cin >> K;

  std::vector<int> C(K);
  std::vector<int> D(K);
  for (size_t i = 0; i < K; i++) {
    std::cin >> C[i] >> D[i];
  }

  int count = 0;
  size_t KK = (size_t)std::pow(2, K);
  for (size_t j = 0; j < KK; ++j) {
    bool n[N+1] = {};
    for (size_t i = 0; i < K; i++) {
      n[j&(1<<i) ? C[i] : D[i]] = true;
    }
    int c = 0;
    for (size_t i = 0; i < M; i++) {
      if (n[A[i]] && n[B[i]]) {
        c++;
      }
    }
	count = std::max(count, c);
  }

  std::cout << count;
  return 0;
}