#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int b[N];

void insert(int l,int r,int c){
    b[l] += c;
    b[r+1] -= c;
}

int main(){

    int n,k;
    cin >> n >> k;

    for(int i=1;i<=n;i++){
        insert(i,i,0);   //构造差分数列
    }

    while(k--){
        int l,r;
        cin >> l >> r;
        if(l > r){
            swap(l,r);
        }
        insert(l,r,1);
    }
    for(int i=1;i<=n;i++){
        b[i] += b[i-1];   //差分还原成前缀和数列
    }

    sort(b+1,b+1+n);

    cout << b[n/2 + 1] << endl;   //差分数列下标从1开始，故"n/2+1"

    return 0;
}