#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=50,B=13,p13=1594323;
bool e[N+1][N+1];
int p[B],dp[2][p13];
int main()
{
	int n,m,a,b,i,j,k,l,o,q,ans;
	for (scanf("%d%d",&n,&m);m;m--)
	{
		scanf("%d%d",&a,&b);
		e[max(a,b)][min(a,b)]=1;
	}
	p[0]=1;
	for (i=1;i<B;i++) p[i]=p[i-1]*3;
	dp[0][0]=1;
	for (i=1;i<=n;i++) for (j=0;j<p13;j++)
	{
		dp[i&1][j]=0;
		k=j%3;
		for (l=0;l<3;l++)
		{
			o=(j+l*p13)/3;
			if (dp[!(i&1)][o])
			{
				for (q=max(i-B,1);q<i&&(k+o/p[i-q-1]%3!=3||!e[i][q]);q++);
				if (q==i) dp[i&1][j]=dp[i&1][j]+dp[!(i&1)][o]&3;
			}
		}
	}
	ans=3;
	for (i=0;i<p13;i++) ans=ans+dp[n&1][i]&3;
	printf("%d",ans>>1);
	return 0;
}