#include<iostream>
#include<map>
#include<vector>
using namespace std;
typedef long long li;
#define maximize(a,b) (a<(b)?a=(b),1:0)
#define rep(i,n) for(li i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << " ";
    cout << *(itr++);
  }
  return os;
};

// pair 型
template<class S,class T>
std::ostream& operator<<(std::ostream& os, const pair<T,S>& p){
  cout << "(" << p.first << "," << p.second << ")";
  return os;
}


int main(){
  int n,m; cin >>n >>m;
  vector<pair<int,int>> cond(m);
  rep(i,m){
    int a,b; cin >>a >>b; a--; b--;
    cond[i]={a,b};
  }
  
  auto ts=[&](vector<int>& sara){
       int cnt=0;
       rep(i,m){
         int f=cond[i].first,s=cond[i].second;
         cnt+=sara[f]&sara[s];
       }
       return cnt;
     };
  
  int k ; cin >>k; 
  vector<int> c(k),d(k);
  rep(i,k){
    int cc,dd; cin >>cc >>dd; cc--; dd--;
    c[i]=cc; d[i]=dd;
  }
  li lim=1LL<<k;
  int ans=0;
  rep(bs,lim){
    vector<int> sara(n,0);
    rep(i,k){
      if(bs&(1LL<<i)){
        sara[c[i]]|=1;
      }else{
        sara[d[i]]|=1;
      }
    }
    if(maximize(ans,ts(sara))){
      if(df)(print(sara,ans));
    }
  }
  
  print(ans);
}

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

ll f[110],n;
int m;
vi ans,a;

int main()
{
    f[0]=1;f[1]=1;m=88;
    rep(i,2,m) f[i]=f[i-2]+f[i-1];
    //rep(i,1,10) cout << f[i] << " ";cout << endl;
    n=readll();
    per(i,m,1)
    {
        if (n>=f[i]) {n-=f[i];a.pb(i);}
    }
    int siz=a.size();
    int len=(a[0]+1)/2,pos=siz-1;
    //rep(i,0,siz-1) printf("%d ",a[i]);puts("");
    rep(i,1,len)
    {
        ans.pb(3);ans.pb(4);
        while ((pos>=0) && ((a[pos]+1)/2==i))
        {
            if (a[pos]&1) ans.pb(2);else ans.pb(1);pos--;
        }
    }
    len=ans.size();
    printf("%d\n",len);
    per(i,len-1,0) printf("%d\n",ans[i]);
    return 0;
}
