#include <fstream>
#include <vector>
#define PII pair<int,int>
#define st first
#define nd second

using namespace std;

ifstream fin("bile.in");
ofstream fout("bile.out");

const int MAXN = 252 , dx[] ={0,-1,1,0} , dy[] = {-1,0,0,1};
int N , TT[MAXN*MAXN] , D[MAXN][MAXN] , dim[MAXN*MAXN] , cmax;
bool u[MAXN][MAXN];

int find(int x)
{
	int R , aux;
	for(R = x;R != TT[R];R = TT[R]);
	for(;TT[x]!=x;)
	{
		aux = TT[x];
		TT[x] = R;
		x = aux;
	}
	return R;
}

void unite(const int &x,const int &y)
{
	if(TT[x]!=y)
		TT[x] = y , dim[y]+=dim[x]  , cmax = max(cmax,dim[y]);
}

int main()
{
	int x , y;
	fin>>N;
	vector<PII> v(N*N);
	vector<int> sol(N*N);
	for(int i=1,count=1;i<=N;++i)
	{
		for(int j=1;j<=N;++j,count++)
		{
		fin>>v[count-1].st>>v[count-1].nd;
		D[i][j] = count , TT[D[i][j] = count] = count , dim[count] = 1;
		}
	
	}
	sol[N*N-1] = cmax;
	u[v[N*N-1].st][v[N*N-1].nd] = 1 , cmax = 1;
	for(int i=N*N-2;i>=0;--i)
	{
		sol[i] = cmax;
		x = D[v[i].st][v[i].nd];
		u[v[i].st][v[i].nd] = 1;
		for(int k=0;k<4;++k)
		{
			if(u[v[i].st + dx[k]][v[i].nd + dy[k]])
				{
				y = D[v[i].st + dx[k]][v[i].nd + dy[k]];
				unite(find(x),find(y));
				}
		}
	}
	for(int i=0;i<N*N;++i)
		fout<<sol[i]<<'\n';
	return 0;
}