#include <bits/stdc++.h>

using namespace std;

const int N = 1e6;
  
void timeS( const char *s = 0 ) { fprintf(stderr, "time = %.2f : %s\n", 1. * clock() / CLOCKS_PER_SEC, s ? s : ""); }

template <class T = int> inline T readInt(); 

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

void solve() {
  int cc = 0, n, m;
  n = readInt();
  m = readInt();
  vector<int> a(m), b(m), deg(n, 0);
  assert(n <= N);
  forn(i, m) {
    a[i] = readInt() - 1;
    b[i] = readInt() - 1;
    deg[a[i]]++;
    deg[b[i]]++;
  }
  vector<int> colors(n, 0);
  vector<int> c[n];

  // colors[v] = 0 -- не покрашена
  // colors[v] = 1
  // colors[v] = 2
  // N <= 10^6, M <= 10^6
  function<void(int,int)> dfs = [&]( int v, int color ) {
    if (colors[v]) return;
    colors[v] = color;
    for (int x : c[v]) dfs(x, 3 - color);
  };
  forn(i, n)
    c[i].reserve(deg[i]);
  forn(i, m) {
    c[a[i]].push_back(b[i]);
    c[b[i]].push_back(a[i]);
  }
  timeS("read and build");
  for (int i = 0; i < n; i++)
    if (!colors[i])
      cc++, dfs(i, 2);
  timeS("dfs");
}

/** Read */

static const int buf_size = 4096;

inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len)
    pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len)
    return -1;
  return buf[pos++];
}

inline int readChar() {
  int c = getChar();
  while (c <= 32)
    c = getChar();
  return c;
}

template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-')
    s = -1, c = getChar();
  while ('0' <= c && c <= '9')
    x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}

int main() {
  solve();
  timeS("end");
}