#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const int MAXN = 5e5 + 100, INF = 1e9;
array<int, 2> tree[MAXN * 4];
int add[MAXN * 4];

array<int, 2> operator*(const array<int, 2>& a, const array<int, 2>& b) {
    array<int, 2> res = min(a, b);
    if (a[0] == b[0]) {
        res[1] = a[1] + b[1];
    }
    return res;
}

void pull(int v) {
    tree[v] = tree[v * 2] * tree[v * 2 + 1];
    tree[v][0] += add[v];
}

void build(int v, int vl, int vr) {
    if (vr - vl == 1) {
        tree[v] = {0, 1};
        return;
    }
    int vm = (vl + vr) / 2;
    build(v * 2, vl, vm);
    build(v * 2 + 1, vm, vr);
    pull(v);
}

void update(int v, int vl, int vr, int l, int r, int val) {
    if (l >= vr || r <= vl) return;
    if (l <= vl && r >= vr) {
        tree[v][0] += val;
        add[v] += val;
        return;
    }
    int vm = (vl + vr) / 2;
    update(v * 2, vl, vm, l, r, val);
    update(v * 2 + 1, vm, vr, l, r, val);
    pull(v);
}

array<int, 2> get(int v, int vl, int vr, int l, int r) {
    if (l >= vr || r <= vl) return {INF, 0};
    if (l <= vl && r >= vr) return tree[v];
    int vm = (vl + vr) / 2;
    auto res1 = get(v * 2, vl, vm, l, r);
    auto res2 = get(v * 2 + 1, vm, vr, l, r);
    auto res = res1 * res2;
    res[0] += add[v];
    return res;
}

unordered_map<int64_t, bool> mp;

void rev_edge(int u, int v) {
    if (u > v) swap(u, v);
    int64_t h = 1ll * u * MAXN + v;
    mp[h] ^= 1;
}

bool cmp(int u, int v) {
    bool inv = false;
    if (u > v) {
        swap(u, v);
        inv = true;
    }
    int64_t h = 1ll * u * MAXN + v;
    bool res = mp[h];
    if (inv) res = !res;
    return res;
}

const int S = 1e3;
int G[S][S];
vector<int> g[S], e[S];

vector<int> top;
int used[MAXN];

void dfs(int v) {
    used[v] = 1;
    for (int u : g[v]) {
        if (!used[u]) {
            dfs(u);
        }
    }
    top.push_back(v);
}

void col(int v) {
    used[v] = 1;
    for (int u : e[v]) {
        if (!used[u]) {
            col(u);
        }
    }
}

int calc(int n) {
    for (int i = 0; i < n; ++i) {
        g[i].clear();
        e[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (G[i][j]) {
                g[i].push_back(j);
                e[j].push_back(i);
            }
        }
    }
    top.clear();
    fill(used, used + n, 0);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }
    reverse(top.begin(), top.end());
    fill(used, used + n, 0);
    int ans = 0;
    for (int v : top) {
        if (!used[v]) {
            ++ans;
            col(v);
        }
    }
    return ans;
} 


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    vector<int> val(n);
    vector<int> id = p;

    build(1, 0, n - 1);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            G[i][j] = 1;
        }
    }

    while (q--) {
        int u, v;
        cin >> u >> v;
        /// v = rand() % (n - 1) + 2;
        /// u = rand() % (v - 1) + 1;
        /// cerr << u << " " << v << endl;
        --u; --v;
        swap(G[u][v], G[v][u]);
        rev_edge(u, v);
        int l = min(id[u], id[v]);
        int r = max(id[u], id[v]);
        /// cerr << l << " " << r << endl;
        if (!cmp(p[l], p[r])) {
            update(1, 0, n - 1, l, r, -1);
            val[p[l]]--;
            val[p[r]]++;
        } else {
            /// cerr << "add" << endl;
            /// cerr << l << " " << r << " " << 1 << endl;
            update(1, 0, n - 1, l, r, 1);
            val[p[l]]++;
            val[p[r]]--;
        }
        if (r == l + 1) {
            for (int s = r; s < n && cmp(p[s - 1], p[s]); ++s) {
                for (int i = s; i > 0 && cmp(p[i - 1], p[i]); --i) {
                    /// cerr << i - 1 << ": " << val[p[i]] - val[p[i - 1]] + 1 << endl;
                    update(1, 0, n - 1, i - 1, i, val[p[i]] - val[p[i - 1]] + 1);
                    ++val[p[i]];
                    --val[p[i - 1]];
                    swap(p[i], p[i - 1]);
                    swap(id[p[i]], id[p[i - 1]]);
                }   
            }
            /**for (int i = r + 1; i < n && cmp(p[i - 1], p[i]); ++i) {
                /// cerr << i - 1 << ": " << val[p[i]] - val[p[i - 1]] + 1 << endl;
                update(1, 0, n - 1, i - 1, i, val[p[i]] - val[p[i - 1]] + 1);
                ++val[p[i]];
                --val[p[i - 1]];
                swap(p[i], p[i - 1]);
                swap(id[p[i]], id[p[i - 1]]);
            }*/
        }
        /**for (int v : p) {
            cerr << v << " ";
        }
        cerr << endl;*/
        auto res = get(1, 0, n - 1, 0, n - 1);
        int cnt = res[1];
        if (res[0] != 0) {
            cnt = 0;
        }
        /**if (cnt + 1 != calc(n)) {
            cout << "bad! " << cnt + 1 << " " << calc(n) << endl;
            return 0;
        }*/
        cout << cnt + 1 << "\n";
    }
    
    return 0;
}