2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 const int MAX = 1e3+10;
 8 int deg[MAX];
 9 struct edge
10 {
11     int from,to;
12 };
13 vector<edge> ans[MAX];
14 int vis[MAX];
15 int G[MAX][MAX];
16 void dfs(int u,int n)
17 {
18     vis[u]=1;
19     for(int i=1;i<=n;i++) if(!vis[i]&&G[u][i])
20     dfs(i,n);
21 }
22 int main()
23 {
24     int n,m; int a,b,start;
25     while(scanf("%d",&n)==1&&n)
26     {
27         scanf("%d",&m);
28         memset(G,0,sizeof(G));
29         memset(deg,0,sizeof(deg));
30         memset(vis,0,sizeof(vis));
31         for(int i=0;i<m;i++)
32         {
33             scanf("%d %d",&a,&b);
34             G[a][b]++; G[b][a]++;
35             deg[a]++; deg[b]++;
36 
37             start=a;
38         }
39         int flag=1;
40         for(int i=1;i<=n;i++) if(deg[i]%2==1){flag=0; break; }
41         if(flag)
42         {
43             dfs(start,n);
44             for(int i=1;i<=n;i++) if(!vis[i]) {flag=0; break; }
45         }
46         if(flag) printf("1\n");
47         else printf("0\n");
48     }
49 }