#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<pair<int,int>>edge;
int root;
bool dfs(int now){
  if(tree[now].empty())return false;
  int ch=(edge[now].second-edge[now].first-1)%2;
  bool f[2]={false,false};
  for(auto x:tree[now]){
    f[dfs(x)]=true;
    ch^=(edge[x].second-edge[x].first-1)%2;
  }
  if(f[1]&&(f[0]|ch)){
    puts("5");
    exit(0);
  }
  return f[0];
}
int main(){
  int i,N,M;
  cin>>N>>M;
  tree.resize(M);
  edge.resize(M);
  if(M==0){
    putchar('4'+N%2);
    putchar('\n');
    return 0;
  }
  vector<int> ver;
  map<pair<int,int>,int> edgenum;
  for(int i=0;i<M;++i){
    int u,v;
    cin>>u>>v;
    --u;--v;
    edge[i]=pair<int,int>(u,v);
    edgenum[edge[i]]=i;
    ver.emplace_back(u);
    ver.emplace_back(v);
  }
  sort(ver.begin(),ver.end());
  ver.erase(unique(ver.begin(),ver.end()),ver.end());
  for(size_t i=0;i<ver.size();++i){
    if(!edgenum.count(minmax(ver[i],ver[(i+1)%ver.size()]))){
      puts("5");
      return 0;
    }
    if((ver[(i+1)%ver.size()]+N-ver[i])%N%2!=1){
      puts("5");
      return 0;
    }
  }
  if(int(ver.size())==M){
    puts("4");
    return 0;
  }
  {
    edgenum.clear();
    for(auto& [l,r]:edge){
      l=lower_bound(ver.begin(),ver.end(),l)-ver.begin();
      r=lower_bound(ver.begin(),ver.end(),r)-ver.begin();
    }
    for(int i=0;i<M;++i)edgenum[edge[i]]=i;
  }
  vector<pair<int,int>> kukan=edge;
  sort(kukan.begin(),kukan.end(),[](pair<int,int> l,pair<int,int> r){
    return l.first!=r.first?l.first<r.first:l.second>r.second;
  });
  vector<pair<int,int>> rootlis;
  for(auto x:kukan){
    auto [l,r]=x;
    if(rootlis.empty()){
      rootlis.emplace_back(x);
      continue;
    }
    while(rootlis.size()&&rootlis.back().second<=l)rootlis.pop_back();
    assert(rootlis.size());
    tree[edgenum[rootlis.back()]].emplace_back(edgenum[x]);
  }
  root=edgenum[kukan[0]];
  if(dfs(root))puts("4");
  else puts("5");
}