#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("bile.in");
ofstream out("bile.out");
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
int mat[300][300];
int l1[300],c1[300];
int val[162520],tt[162520];
vector <int> sol;
inline int findt(int x);

int main()
{
    int a,b,c,n,i,j,k,x,y,d,poz,xn,yn,ma;
    in>>n;
    for(i=1;i<=n*n;i++)
    {
        in>>l1[i]>>c1[i];
    }
    mat[l1[n*n]][c1[n*n]]=1;
    val[(l1[n*n]-1)*n+c1[n*n]]=1;
    tt[(l1[n*n]-1)*n+c1[n*n]]=(l1[n*n]-1)*n+c1[n*n];
    ma=1;
    sol.push_back(0);
    sol.push_back(1);
    for(i=n*n-1;i>=1;i--)
    {    x=l1[i];
         y=c1[i];
         poz=(l1[i]-1)*n+c1[i];
         tt[poz]=poz;
         mat[x][y]=1;
         val[poz]=1;
         int loc=0;
        for(d=0;d<=3;d++)
        {
            xn=x+dx[d];
            yn=y+dy[d];
            if(mat[xn][yn]==1)
                {int tata=findt((xn-1)*n+yn);
                    if(tt[tata]!=poz)loc+=val[tata];
                    tt[tata]=poz;
                }
        }
        val[poz]=max(val[poz],loc+1);
        if(val[poz]>ma){sol.push_back(val[poz]);ma=val[poz];}
        else sol.push_back(ma);

    }
    sol.pop_back();
    while(!sol.empty())
    {  out<<sol.back()<<'\n';
      sol.pop_back();
    }



    return 0;
}
inline int findt(int x)
{  if(tt[x]==x)
return x;
int t=findt(tt[x]);
    tt[x]=t;
    return t;
}