#include    <iostream>
#include    <fstream>
#include    <vector>

using namespace std;

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

vector < int > V;

const int LIMIT = 62505; // 250 la patrat + 5 c8ed4d

int N;
int Height[LIMIT], Father[LIMIT], Avaiable[LIMIT];
int MaxHeight = 0;

inline int Convert(int x, int y)
{
    if(x == 0 || y == 0)
        return -1;
    return (x - 1) * N + y;
}

void ShowConvertor()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cout << Convert(i,j) << " ";
        }
        cout << "\n";
    }
}

void Read()
{
    fin >> N;

    for(int i = 1; i <= N * N; i++)
    {
        int _x, _y;
        fin >> _x >> _y;

        int Value = Convert(_x, _y);
        Height[Value] = 1;
        Father[Value] = Value;
        V.push_back(Value);
    }

}

int Root(int x)
{
    int rOOT, aux;
    while(x != Father[x])
        x = Father[x];

    rOOT = x;
    while(x != Father[x])
    {
        aux         = Father[x];
        Father[x]   = rOOT;
        x           = aux;
    }
    return rOOT;
}

void Unite(int x, int y)
{
    if(Height[x] > Height[y])
        Father[y] = x;
    else
        Father[x] = y;

    if(Height[x] == Height[y])
    {
        Height[y] += 1;
        if(Height[y] > MaxHeight)
            MaxHeight = Height[y];
    }
}

inline int isNeighbor(int p1, int p2)
{
    if(p1 == (p2 - 1))
        return 1;
    if(p1 == (p2 + 1))
        return 1;
    if(p1 == (p2 + N))
        return 1;
    if(p1 == (p2 - N))
        return 1;
    return 0;
}

void checkForUnite(int x)
{
    for(int i = 1; i <= N * N; i++)
        if((Avaiable[i]) && (isNeighbor(i,x)) && (Root(x) != Root(i)))
            Unite(x, i);
}

void Solve()
{
    for(int i = V.size() - 1; i >= 0; i--) // fara unsigned ca dadea urat, se pare ca 0 e pe int - se pare ca 0 nu era pe int, ci mai degreaba trecea pe -1
    {
        Avaiable[i] = 1;
        checkForUnite(V[i]);
        fout << MaxHeight << "\n";
    }
}

int main()
{
    Read();
    Solve();
    //ShowConvertor();
    return 0;
}