#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[(r) + 1]
using namespace std;
void file(){
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
}
using ll = long long;
const int sMax = 4'782'969;
int n, m;
array<int, 16> pw;
array<vector<int>, 55> g;
bitset<sMax> f, tf;
int main(){
//  file();
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  pw[0] = 1;
  for(int i = 1; i <= 15; i++) pw[i] = 3 * pw[i - 1];
  for(int i = 1, u, v; i <= m; i++){
    cin >> u >> v;
    if(u < v) swap(u, v);
    g[u].push_back(v);
  }
  tf[0] = 1;
  bool rs = 0;
  for(int i = 0; i <= n; i++, tf = f){
    f.reset();
    for(int S = 0; S < sMax; S++){
      if(!tf[S]) continue;
      if((S % 3) == 1) rs ^= 1;
      vector<int> cnt(3, 0);
      for(int to : g[i + 1]) cnt[(S / pw[i - to]) % 3]++;
      if(!cnt[2]) f[(S * 3 + 1) % sMax] = 1;
      if(!cnt[1]) f[(S * 3 + 2) % sMax] = 1;
      f[(S * 3) % sMax] = 1;
    }
  }
  cout << rs << "\n";
  return 0;
}