#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 10;
#define fi first
#define se second
pair<pair<int, int> , int>p[MAX];
int a[MAX], b[MAX], t[MAX];
map<pair<int, int> , int>cnt;
bool dentro(pair<pair<int, int> , int> &p1, pair<pair<int, int> , int> &p2){
    return p1.fi.fi >= p2.fi.fi && p1.fi.se <= p2.fi.se;
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i){
        scanf("%d %d", &p[i].fi.fi, &p[i].fi.se);
        cnt[make_pair(p[i].fi.fi, p[i].fi.se)]++;
        p[i].se = i + 1;
    }
    for(int i = 0; i < m; ++i)a[p[i].fi.fi]++, a[p[i].fi.se+1]--;
    int ac = 0;
    for(int i = 1; i <= n; ++i){
        ac += a[i];
        b[i] = ac;
    }
    sort(p, p+m, [](pair<pair<int, int> , int> & p1, pair<pair<int, int> , int> &p2) {
        if(p1.fi.fi != p2.fi.fi)return p1.fi.fi < p2.fi.fi;
        return p1.fi.se > p2.fi.se;
    });
    vector< pair<pair<int, int> , int> > v;
    v.push_back(p[0]);
    for(int i = 1; i < m; ++i){
        if(dentro(p[i], v[(int)v.size()-1]))continue;
        v.push_back(p[i]);
    }
    int tot = 0;
    for(int i = 1; i <= n; ++i){
        if(b[i] == 1){
            int lf = 0, rg = v.size()-1;
            while(lf <= rg){
                int mid = (lf+rg)/2;
                if( i < v[mid].fi.fi) {
                    rg = mid-1;
                }else if(i > v[mid].fi.se){
                    lf = mid+1;
                }else {
                    t[v[mid].se]++;
                    break;
                }
            }
        }else if(b[i] == 0)++tot;
    }
    for(int i = 0; i < m; ++i)if(cnt[make_pair(p[i].fi.fi, p[i].fi.se)] > 1)t[p[i].se] = 0;
    for(int i = 1; i <= m; ++i)printf("%d\n", tot + t[i]);
    return 0;
}