学步园

/*

HDU 1878 
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都是偶数且该图是连通图。
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图
在一个无向图G 中，若从顶点vi到任意顶点vj有路径相连(当然从vj到vi也一定有路径)，
    则称vi和vj是连通的，此图为连通图。

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define manx 1005
using namespace std;

int g[manx][manx];
int sum[manx];

int main(){
    int n,m;
    while(cin>>n,n){
        cin>>m;
        int a,b;
        memset(g,0,sizeof(g));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            g[a][b]=g[b][a]=1;
            sum[a]++; sum[b]++;
        }
        int flag=0;
        for(int i=1;i<=n;i++){
            if(sum[i]%2) flag=1;
            for(int j=i+1;j<=n;j++){
                if(!g[i][j]) flag=1;
            }
        }
        if(flag) printf("0\n");
        else printf("1\n");
    }
}