#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

const int M=12500;
bitset<M> dp[350005];
pii mae[550005];
int kaku[550005];

bitset<M> solve(int x){
    if(kaku[x]!=-1) return dp[kaku[x]];
    else return solve(mae[x].fi)|solve(mae[x].se);
}

int main(){
    
    memset(kaku,-1,sizeof(kaku));
    int N,Q;cin>>N>>Q;
    for(int i=0;i<N;i++){
        dp[i][i/4]=true;
        kaku[i]=i;
    }
    int tim=N;
    
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    for(int q=0;q<Q;q+=50){
        vii que;
        for(int i=q;i<min(Q,q+50);i++){
            int a,b;cin>>a>>b;a--;b--;
            que.pb(mp(a,b));
        }
        vl re;
        for(int i=q;i<min(Q,q+50);i++){
            auto [a,b]=que[i-q];
            auto res=solve(a)|solve(b);
            re.pb(res.count());
            int t=rng()&1;
            if(t){
                dp[tim]=res;
                kaku[N+i]=tim;tim++;
            }else{
                mae[N+i]=mp(a,b);
            }
        }
        for(int i=0;i<si(re);i++){
            cout<<re[i]<<"\n";
        }
        cout<<endl;
    }
}