#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;

int n;

__inline__ int Level(int v) {
    int x = 0;
    while (v > 0) {
        v >>= 1;
        x++;
    }
    return x;
}

__inline__ int Lca(int a, int b) {
    if (Level(a) < Level(b)) swap(a, b);
    while (Level(a) > Level(b)) a >>= 1;
    while (a != b) {
        a >>= 1;
        b >>= 1;
    }
    return a;
}

__inline__ bool isLeaf(int v) {
    return v * 2 > n;
}

unordered_set<int> connectedLeft;
unordered_set<int> connectedRight;
unordered_set<int> connectedBetween;
unordered_set<int> good;

__inline__ void Check(int v) {
    if (isLeaf(v)) return;
    if (connectedLeft.count(v) + connectedRight.count(v) + connectedBetween.count(v) >= 2) {
        good.insert(v);
    } else if (connectedBetween.count(1)) {
        good.insert(1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> n >> m;
    if (n <= 2) {
        m++;
        while (m--) {
            cout << "0\n";
        }
        return 0;
    }
    int sum = 0;
    int full = 1;
    while (n >= full + sum) {
        sum += full;
        full <<= 1;
    }
    int rem = n - sum;
    int lastFullLvl = (full >> 1);
    int leaves = rem + (lastFullLvl - (rem + 1) / 2);
    cout << n - leaves << "\n";
    if (rem & 1) {
        connectedRight.insert(sum - lastFullLvl + (rem + 1) / 2);
    }
    int a, b;
    while (m--) {
        cin >> a >> b;
        if (a / 2 == b || b / 2 == a) {
            cout << n - leaves - good.size() << "\n";
            continue;
        }
        int c = Lca(a, b);
        if (c != a && c != b) {
            connectedBetween.insert(c);
            Check(c);
        }
        while (a / 2 > c) {
            if (a & 1) {
                connectedRight.insert(a / 2);
            } else {
                connectedLeft.insert(a / 2);
            }
            Check(a / 2);
            a /= 2;
        }
        while (b / 2 > c) {
            if (b & 1) {
                connectedRight.insert(b / 2);
            } else {
                connectedLeft.insert(b / 2);
            }
            Check(b / 2);
            b /= 2;
        }
        cout << n - leaves - good.size() << "\n";
    }
}