#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> cant;

/*int comb(int n, int k) {
    string b(k, 1);
    b.resize(n, 0);
    int ans = 0;
    do {
        set<int> d;
        for(int i = 0; i < n; i++) {
            if(b[i]) {
                d.insert(i + 1);
            }
        }
        for(auto k : cant) {
            if(d.count(k.first) != 0 and d.count(k.second) != 0) {
                ans++;
                break;
            }
        }
    } while(prev_permutation(b.begin(), b.end()));
    return ans;
}*/

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cant.push_back({a, b});
    }
    if(m == 0) {
        cout << (1 << n) - 1 << "\n";
        return 0;
    }
    int ans = (1 << n) - 1;
    /*ans -= cant.size();
    for(int i = 3; i <= n; i++) {
        ans -= comb(n, i);
    }*/
    for(int i = 0; i < (1 << n); i++) {
        set<int> d;
        int t = 1;
        int p = i;
        while(i > 0) {
            if(i & 1) {
                d.insert(t);
            }
            t++;
            i >>= 1;
        }
        i = p;
        for(auto k : cant) {
            if(d.count(k.first) != 0 and d.count(k.second) != 0) {
                ans--;
                break;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}