#include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<algorithm>
#include<bitset>
#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], 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(dep[i] == 2) 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();
}

answer.code:20:1: error: ‘mt19937_64’ does not name a type
   20 | mt19937_64 rng;
      | ^~~~~~~~~~
answer.code: In function ‘const std::bitset<12500>& calc(int)’:
answer.code:34:24: warning: reference to local variable ‘t’ returned [-Wreturn-local-addr]
   34 |                 return t;
      |                        ^
answer.code:29:31: note: declared here
   29 |                 bitset<12500> t = calc(rch);
      |                               ^
answer.code:39:24: warning: reference to local variable ‘t’ returned [-Wreturn-local-addr]
   39 |                 return t;
      |                        ^
answer.code:37:31: note: declared here
   37 |                 bitset<12500> t = calc(rch);
      |                               ^
answer.code: In function ‘int main()’:
answer.code:64:9: error: ‘rng’ was not declared in this scope
   64 |         rng = mt19937_64(seed);
      |         ^~~
answer.code:64:15: error: ‘mt19937_64’ was not declared in this scope
   64 |         rng = mt19937_64(seed);
      |               ^~~~~~~~~~