#include <bits/stdc++.h>
usingnamespacestd;#define f first
#define s second
intN,M;constintMaX=100001;vector<int>occ(MaX,0);intans=0;vector<pair<int,int>>cows(MaX);intmain(){ifstreamcin("cereal.in");ofstreamcout("cereal.out");cin>>N>>M;for(inti=0;i<N;i++){intF,S;cin>>F>>S;cows[i].f=F;cows[i].s=S;}vector<int>ansVec(N);for(inti=N-1;i>=0;i--){intpos=cows[i].f;intj=i;while(true){if(occ[pos]==0){occ[pos]=j;ans++;break;}elseif(occ[pos]<j){break;}else{intnext=occ[pos];occ[pos]=j;if(pos==cows[next].s){break;}j=next;pos=cows[next].s;}}ansVec[i]=ans;}for(inti=0;i<N;i++){cout<<ansVec[i]<<endl;}}