#include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 int map[];

 int prim[];

 int find(int n) {

     return prim[n]==n? n:(prim[n] = find(prim[n]));

 }

 int main() {

     int n,m,x,y;

     while(scanf("%d",&n)&&n) {

         scanf("%d",&m);

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

         prim[i] = i;

         memset(map,,sizeof(map));

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

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

             map[x]++;

             map[y]++;

             if(x>y)

             swap(x,y);

             prim[find(x)] = find(y);

         }

         int flag = ;

         int d = find();

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

             if(find(i) != d) {

                 flag = ;

                 break;

             }

             if(map[i]%) {

                 flag = ;

                 break;

             }

         }

         printf(flag? "1\n":"0\n");

     }

     return ;

 }