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

// @author: sharad_sharma

#define ll                long long
#define ld                long double
#define mod               1000000007
#define inf               1e18
#define pb                push_back
#define all(n)            n.begin(),n.end()
#define loop(i,a,b)       for(int i=(a);i<=(b);i++)
#define logarr(arr)       for(int z=(0);z<(arr.size());z++) cout<<(arr[z])<<" ";cout<<endl;
#define deb(x)            cout << #x << " = " << x << endl
#define debu(x, y)        cout << "( " << #x << ", " << #y << " ) = ( " << x << ", " << y << " )" << endl

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
void file_i_o()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
	#ifndef ONLINE_JUDGE
	    freopen("input.txt", "r", stdin);
	    freopen("output.txt", "w", stdout);
	#endif
}

int N = 25;
vector<vector<int>> adj(N);
vector<int> visited(N, 0);
vector<int> col(N, 0);
vector<int> level(N, 0);

// i want to search exhaustively
int dfs(int i, int p) {
	//if(visited[i]) return 1;
	level[i] = level[p] + 1;
	visited[i] = 1;
	int ret = 1;

	for(auto u: adj[i]) {
		//if(u == p) continue;	// this is not enough if their level is same then it must return 0
		if(level[u] != 0 && level[u] != level[i] + 1) {
			if(col[u] == col[i]) {
				// this should not be allowed
				return 0;
			}	
			continue;
		}
	
		int tem = 0;
		for(int c=1; c<4; c++) {
			if(col[i] == c) continue;
			col[u] = c;
			tem += dfs(u, i);
			col[u] = 0;
		}
		ret *= tem;
	}
	return ret;
}

int32_t main(int32_t argc, char const *argv[]) {
	clock_t begin = clock();
	file_i_o();

	// Write your code here....
	int n, m;
	cin >> n >> m;
	for(int i=0; i<m; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	int ans = 1LL;

	for(int i=0; i<n; i++) {
		if(visited[i]) continue;
		// let's say we colour Red on i so, it's edges is either blue or green
		col[i] = 1;	// let's say Red is 1
		level[i] = 0;
		int dd = dfs(i, i);
		ans = ans*3LL*dd;
	}
	cout << ans << "\n";
	
	#ifndef ONLINE_JUDGE 
	  clock_t end = clock();
	  cout<<"\n\nExecuted In: "<<double(end - begin) / CLOCKS_PER_SEC*1000<<" ms";
	#endif 
	return 0;
}


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX =1000000000000000000;
ll mod= 1000000000;
long double pi=3.141592653589793238;
void pls()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
}
ll n,m,k;
vector<pair<ll,ll>> p,temp;
ll recursion(int i,vector<int> &visi){
   if(i==k)
   {
        ll tot=0;
        for(i=0;i<p.size();i++){
            if(visi[p[i].first] && visi[p[i].second])
              tot++;
            
        }
        return tot;
    }

        visi[temp[i].first]+=1;
        ll val=recursion(i+1,visi);
        visi[temp[i].first]-=1;
        visi[temp[i].second]+=1;
        ll val1=recursion(i+1,visi);
        visi[temp[i].second]-=1;
        return max(val,val1);
   

}
void solve()
{   
          cin>>n>>m;
          for(int i=0;i<m;i++){
            ll x,y; cin>>x>>y;
            p.push_back({x,y});
          }
          cin>>k;
          for(int i=0;i<k;i++){
            ll x,y; cin>>x>>y;
            temp.push_back({x,y});
          }
          vector<int> visi(n+1,0);
          cout<<recursion(0,visi)<<endl;
       
}
int main(){pls(); solve(); return 0;}
/*
  Mostly wrong answer form base case or overflow or runtime 
  Debug--> check overflow---> check varible name---> check logic implementation----> check logic

*/










  