/***************************************************

 题目描述：

         欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？

 输入：

         测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。

 输出：

         每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。

 样例输入：

     3 3

     1 2

     1 3

     2 3

     3 2

     1 2

     2 3

     0

 样例输出：

     1

     0

 **************************************************/

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N =  + ;

 int n, m;

 int g[N][N];

 int degree[N];

 int p[N];

 int union_find(int x);

 void disjoint_union(int a, int b);

 bool check();

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("e:\\uva_in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

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

     {

         if (n == )

             break;

         scanf("%d", &m);

         memset(degree, , sizeof(degree));

         memset(p, -, sizeof(p));

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

             int a, b;

             scanf("%d%d", &a, &b);

             degree[a]++;

             degree[b]++;

             disjoint_union(a, b);

         }

         if (check())

             printf("1\n");

         else

             printf("0\n");

     }

     return ;

 }

 int union_find(int x)

 {

     if (p[x] < )

         return x;

     return p[x] = union_find(p[x]);

 }

 void disjoint_union(int a, int b)

 {

     int pa = union_find(a);

     int pb = union_find(b);

     if (pa == pb)

         return;

     if (pa < pb)

         p[pb] = pa;

     else

         p[pa] = pb;

 }

 bool check()

 {

     int cnt = ;

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

         cnt += (p[i] < );

         if (degree[i] & )

             return false;

     }

     if (cnt != )

         return false;

     return true;

 }

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <stack>

 #include <iostream>

 using namespace std;

 int fa[],degree[];

 int findfa(int a){

     if(fa[a]!=a){

         fa[a]=findfa(fa[a]);

     }

     return fa[a];

 }

 int main(){

     //freopen("D:\\INPUT.txt","r",stdin);

     int n,m;

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

         if(!n){

             break;

         }

         memset(degree,,sizeof(degree));

         scanf("%d",&m);

         int i;

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

             fa[i]=i;

         }

         int u,v;

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

             scanf("%d %d",&u,&v);

             degree[u]++;

             degree[v]++;

             int fu=findfa(u);

             int fv=findfa(v);

             if(fu>fv){

                 fa[fv]=fu;

             }

             else{

                 fa[fu]=fv;

             }

         }

         int num=;

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

             if(fa[i]==i){

                 num++;

             }

         }

         if(num!=){//整体不联通,整个图不止一个集合.好好体会！！

             cout<<<<endl;

             continue;

         }

         int odd=;

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

             if(degree[i]%){

                 odd++;

             }

         }

         if(odd){//不是所有点的度数均为偶数

             cout<<<<endl;

             continue;

         }

         //全图联通并且所有点的度数均为偶数

         cout<<<<endl;

     }

     return ;

 }