//染色法判断二分图
#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 20005, maxm = 100005;
int head[maxn], ver[2 * maxm], Next[2 * maxm], tot, v[maxn];

void add(int x, int y){
    ver[++ tot] = y;
    Next[tot] = head[x], head[x] = tot;
}

bool dfs(int x, int color){
    v[x] = color;
    for(int i = head[x]; i; i = Next[i]){
        int y = ver[i];
        if(!v[y]){
            bool flag = dfs(y, 3 - color);
            if(!flag) return false;
        }
        else if(v[y] == color) return false;
    }
    return true;
}

bool check(){
    memset(v, 0, sizeof(v));
    for(int i = 1; i <= n; ++ i)
        if(!v[i])
            if(!dfs(i, 1)) return false;
    return true;
}

int main()
{
    cin >> n >> m;

    for(int i = 1, x, y; i <= m; ++i){
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    cout << check() <<endl;
    return 0;
}


/**
5 5
1 4
2 3
2 5
4 5
1 3
*/