#include<bits/stdc++.h>
using namespace std;
int n,m,x[100005],y[100005],c1[100005],c2[100005],b1[100005],b2[100005],z[100005];
void add1(int pos,int u)
{
	for(int i=pos;i>0;i-=(i&-i))
		c1[i]+=u; 
} 
int find1()
{
	int sum=0;
	for(int i=1;i<=m;i+=(i&-i))
		sum+=(c1[i]?1:0);
	return sum;
}
void add2(int pos,int u)
{
	for(int i=pos;i>0;i-=(i&-i))
		c2[i]+=u; 
} 
int find2()
{
	int sum=0;
	for(int i=1;i<=m;i+=(i&-i))
		sum+=(c2[i]?1:0);
	return sum;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
		if(b1[x[i]]<=b2[y[i]])
			add1(x[i],1),z[i]=1,b1[x[i]]++;
		else add2(y[i],1),z[i]=2,b2[y[i]]++;
	}
	for(int i=0;i<n;i++)
	{
		cout<<find1()+find2()<<endl;
		if(z[i]==1)
		add1(x[i],-1);
		else
		add2(y[i],-1);
	}
	return 0;
}