#include <cstdio>
#include<iostream> 
using namespace std;
int n,m,cnt,n1[100010],n2[100010],bel[100010],ans[100010];
void search(int x,int y){
    if(!bel[y]){
        bel[y]=x; 
        cnt++;
    }else if(bel[y]>x){ //被编号大的牛拿走
        int tmp=bel[y];
        bel[y]=x;
        if(y==n1[tmp]) 
		   search(tmp, n2[tmp]);
    }
}
int main() {
    freopen("usaco_20Open_cereal.in","r",stdin);
    freopen("usaco_20Open_cereal.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>n1[i]>>n2[i];
    for(int i=n;i>0;i--){
        search(i,n1[i]);
        ans[i-1]=cnt;
    }
    for(int i=0;i<n;i++) cout<<ans[i]<<endl;
    return 0;
}