#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#define maxn 2010

using namespace std;

int f[maxn];

int findf(int x)

{

    if(f[x]==x)

        return x;

    else return findf(f[x]);

}

void join(int x,int y)

{

    int t1,t2;

    t1=findf(x);

    t2=findf(y);

    if(t1!=t2)

        f[t2]=t1;

}

int main()

{

    int n;

    int degree[maxn];

    int m;

    int cnt;

    int x,y;

    int flag;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n==)

            break;

        cnt=,flag=;

        memset(degree,,sizeof(degree));

        for(int i=;i<=n;i++)

            f[i]=i;

        for(int i=;i<=m;i++)

        {

            scanf("%d%d",&x,&y);

            join(x,y);

            degree[y]++;

            degree[x]++;

        }

        for(int i=;i<=n;i++)

        {

            if(f[i]==i)

                cnt++;

        }

        for(int i=;i<=n;i++)

        {

            if(degree[i]%==)

                flag=;

        }

        if(cnt==&&flag==)

            printf("1\n");

        else

            printf("0\n");

    }

    return ;

}