#include<cstdio>
using namespace std;
const int MAXN=100005;
struct note{
	int first;
	int second;
}cow[MAXN];
int have[MAXN],ans[MAXN];
int n,m,num;
void dfs(int k,int want){
	if(!have[want]){
		have[want]=k;
		num++;
	}
	else{
		if(k<have[want]){
			int next=have[want];
			have[want]=k;
			if(want==cow[next].first)
				dfs(next,cow[next].second);
		}
	}
}
int main(){
	freopen("usaco_20Open_cereal.in","r",stdin);
	freopen("usaco_20Open_cereal.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&cow[i].first,&cow[i].second);
	for(int i=n;i>=1;i--){
		dfs(i,cow[i].first);
		ans[i-1]=num;
	}
	for(int i=0;i<n;i++)
		printf("%d\n",ans[i]);
	return 0;
}