• 并查集

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;

#define TEST 1
#if TEST
struct DSU {  // disjoint set union
    vector<size_t> pa, size;
    explicit DSU(size_t size_) : pa(size_ * 2), size(size_ * 2, 1) {
        iota(pa.begin(), pa.begin() + size_, 0);
        iota(pa.begin() + size_, pa.end(), size_);
    }
    void show(size_t size_) {
        int weight = 3;
        size_ = min(size_, size.size());
        std::cout << left << "     i  : ";
        for (int i = 0; i < size_; i++)
            std::cout << setw(weight) << i << " \n"[i == size_ - 1];
        std::cout << left << "  pa[i] : ";
        for (int i = 0; i < size_; i++)
            std::cout << setw(weight) << pa[i] << " \n"[i == size_ - 1];
        std::cout << left << "size[i] : ";
        for (int i = 0; i < size_; i++)
            std::cout << setw(weight) << size[i] << " \n"[i == size_ - 1];
    }
    size_t find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }
    void unite(size_t x, size_t y) {
        x = find(x), y = find(y);
        if (x == y)
            return;
        // if (size[x] < size[y]) swap(x, y);
        pa[y] = x;
        size[x] += size[y];
    }
    void erase(size_t x) {
        --size[find(x)];
        pa[x] = x;
    }
    void move(size_t x, size_t y) {
        auto fx = find(x), fy = find(y);
        if (fx == fy)
            return;
        pa[x] = fy;
        --size[fx], ++size[fy];
    }
};
#endif

void solve() {
    int n, m, k, l, r;
    cin >> n >> m;
    DSU dsu(n + 2);
    int ans = n;
    while (m--) {
        cin >> l >> r;
        int x = dsu.find(l);
        while (x <= r) {
            dsu.unite(x + 1, x);  // 向右合并，pa[x] = x+1
            x = dsu.find(x);
            ans--;
        }
        cout << ans << "\n";
    }
}
int main() {
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}