#include<fstream>


using namespace std;



ifstream f("bile.in");
ofstream g("bile.out");
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int T[dim*dim],M[dim*dim],a[dim][dim],r[dim*dim],c[dim*dim],i,j,x,y,a,b,Max,ic,jc,p,ww,aa,d;
int tata (int x){
	int y=x;
	while(T[y]>=0)
		y=T[y];
	return y;
}
int main (){
	f>>n;
	
	
	for(i=n*n;i>=1;--i)
		f>>r[i]>>c[i];
	
	
	for(i=1;i<=n*n;++i)
		T[i]=-1;
	Max=0;
	for(i=1;i<=n*n;++i){
		M[i]=Max;
		x=r[i];
		y=c[i];
		p=(x-1)+y;
		a[x][y]=1;
		ww=tata(p);
		
		for(d=0;d<=3;d++){
			
			ic=x+dx[d];
			jc=y+dy[d];
			
			if(ic>=1 && ic<=n && jc>=1 && jc<=n && a[ic][jc]==1){
				
				p=(ic-1)+jc;
				
				aa=tata(p);
				
				T[ww]+=T[aa];
				T[aa]=ww;
				if(Max<-T[ww])
					Max=-T[ww];
			}
		}
	}
	
	for(i=n*n;i>=1;--i)
		g<<M[i]<<"\n";
	return 0;
}