//
//  na 2400-re.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/14.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <random>
#include <time.h>
using namespace std;
//#define RNDDATA
//#define BBBBIG
const int maxn = 2e5 + 5, maxm = 2e5 + 5;
#if defined(MAC_OS_VERSION_11_0) && !defined(BBBBIG)
const int maxv = 10 * 4, maxe = 10 * 8;
#else
const int maxv = maxm * 4, maxe = maxm * 8;
#endif
int dep[maxv], ec[maxe * 2], en, S, E, saved[maxe * 2];
vector<int> to[maxv], ei[maxv];
struct Edge{
    int u, v, w;
    Edge(int u, int v, int w): u(u), v(v), w(w) {}
    inline bool operator < (const Edge &other) const{
        return w > other.w;
    }
};
vector<Edge> es;
inline void real_edge(int u, int v, int w){
    to[u].push_back(v);
    to[v].push_back(u);
    ei[u].push_back(en);
    ei[v].push_back(en ^ 1);
    ec[en] = w;
    ec[en ^ 1] = 0;
    en += 2;
}
inline void edge(int u, int v, int w){
//    cerr << u << ' ' << v << ' ' << w << endl;
//    es.push_back(Edge(u, v, w));
    real_edge(u, v, w);
}
int que[maxv], qs, qe;
inline bool bfs(){
    for(int i = 0; i <= E; ++i)
        dep[i] = 0;
    dep[S] = 1;
    qs = 0;
    qe = 0;
    que[qe++] = S;
    int node, nn;
    while(qs < qe){
        node = que[qs++];
        for(int i = 0; i < to[node].size(); ++i){
            nn = to[node][i];
            if(!dep[nn] && ec[ei[node][i]] > 0){
                dep[nn] = dep[node] + 1;
                if(nn == E)
                    return true;
                que[qe++] = nn;
            }
        }
    }
    return false;
}
int dinic(int node, int flow){
    if(node == E)
        return flow;
    int unf = flow, nn, nw, nf;
    for(int i = 0; i < to[node].size(); ++i){
        nn = to[node][i];
        nw = ec[ei[node][i]];
        if(dep[nn] == dep[node] + 1 && nw > 0){
            nf = dinic(nn, min(nw, unf));
            if(!nf)
                dep[nn] = 0;
            unf -= nf;
            ec[ei[node][i]] -= nf;
            ec[ei[node][i] ^ 1] += nf;
            if(!unf)
                break;
        }
    }
    return flow - unf;
}
int n, m;
const int its_a_me = 4;
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
#ifdef MAC_OS_VERSION_11_0
    time_t st = clock();
#endif
    S = 0;
    E = m * 4 + 1;
    for(int i = 1; i <= m; ++i){
        edge(m * 3 + i, E, 1);
        edge(m * 2 + i, m * 3 + i, 1);
        if(i != 1)
            edge(m * 2 + i, m * 2 + i - 1, i - 1);
        edge(m + i, m * 3 + i, 1);
        if(i != m)
            edge(m + i, m + i + 1, m - i);
        edge(S, i, 1);
    }
#if defined(MAC_OS_VERSION_11_0) && defined(RNDDATA)
    mt19937 rnd(114514);
    uniform_int_distribution<> dist(1, m + 1);
//    if(its_a_me == 4)
//        cerr << "[ " << m / 3 << " " << m * 2 / 3 << " ]" << endl;
#endif
    for(int i = 1; i <= n; ++i){
        int l, r;
#if defined(MAC_OS_VERSION_11_0) && defined(RNDDATA)
        if(its_a_me == 1){
            l = dist(rnd);
            r = dist(rnd);
        }else if(its_a_me == 2){
            l = i;
            r = i;
        }else if(its_a_me == 3){
            l = i;
            r = n - i;
        }else if(its_a_me == 4){
            l = m / 3;
            r = m * 2 / 3;
        }
        if(l > r)
            swap(l, r);
#else
        cin >> l >> r;
#endif
        if(l != 0)
            edge(i, m * 2 + l, 1);
        if(r != m + 1)
            edge(i, m + r, 1);
    }
//    sort(es.begin(), es.end());
    int ans = 0;
    int ptr = 0;
//    for(int clim = (1 << 20); clim; clim >>= 1){
//        while(ptr < es.size() && es[ptr].w >= clim){
//            real_edge(es[ptr].u, es[ptr].v, es[ptr].w);
//            ++ptr;
//        }
        while(bfs()){
            ans += dinic(S, n);
//            for(int i = 0; i < en; ++i)
//                if(i & 1){
//                    saved[i] = ec[i];
//                    ec[i] = 0;
//                }
        }
//    }
    cout << n - ans << endl;
#ifdef MAC_OS_VERSION_11_0
    cerr << "time: " << double(clock() - st) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
    return 0;
}