#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=55;
int n,m;
poly G[N];
int pw[15];
int dp[1594323],tmp[1594323];
void BellaKira()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if (x>y) swap(x,y);
        G[y].push_back(x);
    }
    pw[0]=1;
    for (int i=1;i<=13;i++) pw[i]=pw[i-1]*3;
    dp[0]=1;
    for (int i=1;i<=n;i++)
    {
        memset(tmp,0,sizeof(tmp));
        for (int j=0;j<pw[13];j++) 
            tmp[j]=dp[j/3];
        for (int j=0;j<pw[13];j++)
            if (dp[j])
            {
                int tx=1,ty=1;
                for (auto u:G[i])
                {
                    int x=13-(i-u);
                    if ((j/pw[x])%3==1) tx=0;
                    else if ((j/pw[x])%3==2) ty=0;
                }
                if (tx) tmp[j/3+pw[12]]=(tmp[j/3+pw[12]]+dp[j])&3;
                if (ty) tmp[j/3+pw[12]+pw[12]]=(tmp[j/3+pw[12]+pw[12]]+dp[j])&3;
            }
        memcpy(dp,tmp,sizeof(dp));
    }
    int ans=0;
    for (int i=0;i<pw[13];i++) ans=(ans+dp[i])&3;
    ans=(ans+3)%4;
    cout<<ans/2<<'\n';
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}