#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int S=1594323,N=53;
int n,m;
bitset<S> f,g;
int msk1[S],msk2[S];
int pw[N],adj[N];
int main(){
	n=read();m=read();pw[0]=1;
	for(int i=1;i<=n;++i) pw[i]=pw[i-1]*3;
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		if(u>v) swap(u,v);
		adj[v]|=1<<(v-u-1);
	}
	for(int s=1;s<pw[n];++s){
		msk1[s]=(msk1[s/3]<<1)|((s%3)==1);
		msk2[s]=(msk2[s/3]<<1)|((s%3)==2);
	}
	f.set(0);
	bool res=1;
	for(int i=1;i<=n;++i){
		g=f;f.reset();
		for(int s=g._Find_first();s!=S;s=g._Find_next(s)){
			int t=s*3;
			while(t>=pw[n]) t-=pw[n];
			f.flip(t);
			if(!(msk2[s]&adj[i])) f.flip(t+1);
			if(!(msk1[s]&adj[i])) f.flip(t+2);
		}
		if(i>1){
			for(int s=f._Find_first();s!=S;s=f._Find_next(s))
				if(s%3==1) res^=1;
		}
	}
	printf("%d\n",res);
	return 0;
}