// HDU-1878
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define F(i,a,b)  for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 1e3+10;

int father[N];
int Find(int c)
{
    int p=c,i=c,j;
    while(father[p]!=p)  p=father[p];
    while(father[i]!=p) {
        j=father[i], father[i]=p, i=j;
    }
    return p;
}
bool Unite(int u,int v)
{
    int fau=Find(u), fav=Find(v);
    if(fau!=fav) { father[fav]=fau; return true; }
    return false;
}

int degree[N];
int main()
{
    int n, m;
    while(scanf("%d", &n) && n) {
        scanf("%d", &m);
        mes(degree, 0);
        FF(i,1,n) father[i]=i;
        FF(i,1,m) {
            int u, v;
            scanf("%d%d", &u, &v);
            if(u!=v) {
                degree[u]++, degree[v]++;
                if(Unite(u, v)) ;
            }
        }
        int flag=0, cnt=0;
        FF(i,1,n) if(degree[i]&1) flag=1;
        FF(i,1,n) if(father[i]==i) cnt++;
        if(flag || cnt>1) puts("0");
        else puts("1");
    }

    return 0;
}