#include <bits/stdc++.h>
using namespace std;
mt19937 rd(233);
using bs = bitset<12500>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> vis(n + q + 1);
    vector<bs> vec(max(1, q * 2 / 3));
    vector<array<int, 2>> fr(n + q + 1);
    vector<int> saveid(n + q + 1, -1);
    int idc = 0, vistag = 0;
    auto search = [&](auto &&self, int x, bs &bs) -> void {
        if (x <= n) {
            bs[(x - 1) >> 2] = 1;
        } else if (vis[x] < vistag) {
            vis[x] = vistag;
            if (saveid[x] == -1) {
                self(self, fr[x][0], bs);
                self(self, fr[x][1], bs);
            } else {
                bs |= vec[saveid[x]];
            }
        }
    };
    for (int i = 1; i <= q; i++) {
        cin >> fr[n + i][0] >> fr[n + i][1];
        bs now;
        ++vistag;
        for (int j = 0; j < 2; j++) {
            int x = fr[n + i][j];
            if (!vis[x] && idc < (int)vec.size() && rd() % 99999 < 66666) {
                saveid[x] = idc++;
                ++vistag;
                search(search, x, vec[saveid[x]]);
                now |= vec[saveid[x]];
            } else {
                search(search, x, now);
            }
        }
        cout << now.count() * 2 << '\n';
        if (i % 50 == 0 || i == n) {
            cout.flush();
        }
    }
    return 0;
}