#include<bits/stdc++.h>
using namespace std;
#define rep2(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define rep(i,j) rep2(i,0,j)
#define rrep2(i,j,k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i,j) rrep2(i,j,0)
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
#define eb emplace_back
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const ll inf=LLONG_MAX/4;
template<typename T>
bool chmin(T& a,T b){return a>b?a=b,1:0;}
template<typename T>
bool chmax(T& a,T b){return a<b?a=b,1:0;}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	ll n,q;cin>>n>>q;
	const ll div=4;
	random_device rnd;
	mt19937_64 mt(rnd());
	vl p(n);
	rep(i,n) p[i]=i;
	shuffle(all(p),mt);
	const ll M=5e4;
	vector<bitset<M/div+1>> bit(n+q);
	rep(i,n) bit[i].set(p[i]/div);
	rep2(i,n,n+q){
		ll x,y;cin>>x>>y;
		x--,y--;
		bit[i]=bit[x]|bit[y];
		cout<<bit[i].count()*2<<"\n";
	}
}