#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int col[N];
vector<int> e[N];

bool dfs(int u, int c) {
  col[u] = c;
  bool res = 1;
  for (auto v : e[u]) {
    if (col[v] == !c) continue;
    if (col[v] == c) return 0;
    res &= dfs(v, !c);
    if (!res) return 0;
  }
  return 1;
}

void solve() {
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].emplace_back(v), e[v].emplace_back(u);
  }
  
  memset(col, -1, sizeof(col));
  if (!dfs(1, 0)) {
    cout << "0\n";
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (col[i] == -1) {
      cout << "0\n";
      return;
    }
  }
  cout << "1\n";
}

int main() {
  
  while (cin >> n >> m) solve();
  
  return 0;
}