bool M1;
#include<bits/stdc++.h>
using namespace std;
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time cerr<<(clock()-ST)*1.0/CLOCKS_PER_SEC<<'\n'
//#define int long long
#define ll long long
#define db double
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
#define fr first
#define sc second
template<typename T> void ckmin(T &x,T y){x=min(x,y);}
template<typename T> void ckmax(T &x,T y){x=max(x,y);}
mt19937 rnd(time(0));
const int N=200005;
const int inf=1e9;
const int mod=1000000007;
int n,m,ans;
int cnte,to[N<<1],nxt[N<<1],head[N];
inline void add(int u,int v){
	to[++cnte]=v;
	nxt[cnte]=head[u];
	head[u]=cnte;
}
bool vis[N];
void dfs(int now,int s){
    if(now==n){
        int tot1=0,tot2=0;
        for(int u=1;u<=n;u++){
            if(!vis[u]) continue;
            tot1++;
            for(int i=head[u];i;i=nxt[i]){
                int v=to[i];
                if(vis[v]) tot2++;
            }
        }
        if(tot1-tot2==1) ans++;
        if(ans>inf) ans%=2;
        return;
    }
    for(int i=s+1;i<=n;i++){
        if(vis[i]) continue;
        vis[i]=1;
        dfs(now+1,i);
        vis[i]=0;
    }
    return;
}
bool M2;
signed main(){
//	look_memory;
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs(0,0);
	cout<<ans%2;
	return 0;
}