#include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<algorithm>
#include<bitset>
#include<random>
#define fopen(x, y) freopen(x".in", "r", stdin); freopen(y".out", "w", stdout);
//#define int long long
#ifdef int
#define inf 0x3f3f3f3f3f3f3f3fll
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;

bitset<12500> s[300000];

int n, q, id[550005], l[550005], r[550005], dep[550005], cnt[550005], m;
mt19937_64 rng;

#define lch l[i]
#define rch r[i]
const bitset<12500>& calc(int i) {
	if(id[i]) return s[id[i]];
	else if(i <= n) { s[0].reset(); s[0].set((i - 1) >> 2); return s[0]; }
	if(lch >= rch) swap(lch, rch);
	if(lch <= n) {
		bitset<12500> t = calc(rch);
		t.set((lch - 1) >> 2);
//		if(i >= 5) {
//			cout << i << ' ' << t.count() << '\n';
//		}
		return t;
	}
	else {
		bitset<12500> t = calc(rch);
		t |= calc(lch);
		return t;
	}
} 
#undef lch
#undef rch

void work() {
	cin >> n >> q;
	for(int i = n + 1; i <= n + q; i++) {
		cin >> l[i] >> r[i];
		dep[i] = max(dep[l[i]], dep[r[i]]) + 1; 
		s[0] = calc(i);
		if(rng() & 1) dep[i] = 0, id[i] = ++m;
		s[id[i]] = s[0];
		cout << s[id[i]].count() * 2 << '\n';
		if((i - n) % 50 == 0) fflush(stdout);
	}
	fflush(stdout);
}

signed main() {
//	ios::sync_with_stdio(false); cin.tie(0);
//	typedef unsigned long long ull;
//	ull seed = (ull)(new char);
//	delete (char*)seed;
//	rng = mt19937_64(seed);
	int _ = 1;
//	cin >> _;
	while(_--) work();
}