#include<iostream>
#include<vector>
using namespace std;
int N,M;
vector<int>G[20];
int col[20];
bool dfs(int u) {
	for(int v:G[u]) {
		if(col[v]==-1) {
			col[v]=3-col[u];
			if(!dfs(v))return false;
		}
		else if(col[u]==col[v])	{
			return false;
		}
	}
	return true;
}

int main() {
	cin>>N>>M;
	vector<pair<int,int> >E(M);
	for(int i=0;i<M;i++) {
		int a,b;cin>>a>>b;
		a--,b--;
		E[i]=make_pair(a,b);
		G[a].push_back(b);
		G[b].push_back(a);
	}

	long ans=0;
	for(int k=0;k<1<<N;k++)	{
		for(int i=0;i<N;i++) {
			col[i]=-1;
			if(k>>i&1)col[i]=0;
		}
		bool ok=true;
		for(pair<int,int>e:E)if(col[e.first]==0&&col[e.second]==0) {
			ok=false;
			break;
		}
		if(!ok)continue;
		int cnt=0;
		for(int i=0;i<N;i++)if(col[i]==-1)	{
			col[i]=1;
			if(!dfs(i))
			{
				ok=false;
				break;
			}
			cnt++;
		}
		if(ok)ans+=1<<cnt;
	}
	cout<<ans<<endl;
}

#include <bits/stdc++.h>

#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

using namespace std;
using ll = long long;
using pii = pair<int, int>;
template<typename... T> void rd(T&... args) {((cin>>args), ...);}
template<typename... T> void wr(T... args) {((cout<<args<<" "), ...);cout<<endl;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin>>n>>m;
    vector<int> a(m), b(m);
    for (int i=0; i<m; i++) {
        cin>>a[i]>>b[i];
        a[i]--;
        b[i]--;
    }
    vector<int> c(n);
    for (auto& i : c) cin>>i;
    vector<bool> ab(m);
    vector<vector<pii>> g(n);
    for (int i=0; i<m; i++) {
        if (c[a[i]]>c[b[i]]) ab[i]=true;
        else if (c[a[i]] < c[b[i]]) ab[i]=false;
        else {
            g[a[i]].emplace_back(b[i], i);
            g[b[i]].emplace_back(a[i], i);
        }
    }
    vector<int> dep(n, -1);
    auto dfs=[&](auto& dfs, int u, int p) -> void {
        for (auto [v, e] : g[u]) {
            if (v==p) continue;
            if (dep[v]==-1) {
                dep[v]=dep[u]+1;
                ab[e]=a[e]==v;
                dfs(dfs, v, u);
            } else if (dep[u]>dep[v]) ab[e]=a[e]==v;
        }
    };
    for (int i=0; i<n; i++) {
        if (dep[i]==-1) {
            dep[i]=0;
            dfs(dfs, i, i);
        }
    }
    for (auto i : ab) cout<<(i ? "->" : "<-")<<'\n';
    return 0;
}

