//无向图的欧拉回路判断
//1.图连通
//2.所有顶点的度为偶数
//有向图的欧拉回路判断
//1.图连通
//2.图中所有节点入度等于出度 

#include<cstdio>
#define N 1005
int father[N];
int num[N];
int findFather(int x){
    if(x == father[x]) return x;
    else{
        int tp = findFather(father[x]);
        father[x] = tp;
        return tp;
    } 
} 

int main(){
    int n,m,x,y;
    while(scanf("%d%d",&n,&m) != EOF){
        if(n==0) break;
        for(int i=1;i<=n;i++){
            father[i] = i;
            num[i] = 0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            num[x]++;
            num[y]++;
            int fax = findFather(x);
            int fay = findFather(y);
            if(fax != fay){
                father[fax] = fay;
            }
        }
        int ans = findFather(1),tag = 1;
        if(num[1]&1) tag = 0; 
        for(int i=2;i<=n;i++){
            if((num[i]&&findFather(i)!= ans)||(num[i]&1)){//1.该顶点存在，同时不连通（根节点不同）说明不是欧拉回路 
                tag = 0;                                   //2.该顶点为奇数（已经包含了顶点存在） 
                break;                                     //所以，总结一下出错的原因：没有考虑该顶点是否存在就直接判断了 
            }
        }
        printf("%d\n",tag);

    }
    return 0;
}