#include <fstream>

using namespace std;

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

const int N = 260;

int n, n2, v[N][N], i, j, p, ip, jp, ii, jj, ij, maxim, minim, k, rj, y, rp;
int Y[N*N];
int X[10];

struct bila{
    int x, y;
} a[N*N];

int pack(int i, int j) {
    return (i - 1) * n + j;
}

void unpack(int x, int &i, int &j) {
    i = (x - 1) / n;
    j = x - i * n;
    i++;
}

int rad(int x){
    int i, j;
    unpack(x, i, j);
    while (v[i][j] > 0) {
        x = v[i][j];
        unpack(x, i, j);
    }
    return pack(i, j);
}

int main(){
    fin >> n;
    n2 = n * n;
    for (i = 1; i <= n2; ++i) {
        fin >> a[i].x >> a[i].y;
    }
    for (i = n2; i > 0; --i) {
        v[a[i].x][a[i].y] = -1;
        k = 1;
        X[1] = pack(a[i].x, a[i].y);
        if (v[a[i].x - 1][a[i].y] != 0) {
            X[++k] = rad(pack(a[i].x - 1, a[i].y));
        }
        if (v[a[i].x + 1][a[i].y] != 0) {
            X[++k] = rad(pack(a[i].x + 1, a[i].y));
        }
        if (v[a[i].x][a[i].y - 1]!=0) {
            X[++k] = rad(pack(a[i].x, a[i].y - 1));
        }
        if (v[ a[i].x ][ a[i].y + 1 ]!=0) {
            X[++k] = rad(pack(a[i].x, a[i].y + 1));
        }
        minim = 0;
        for (j = 1; j <= k; ++j) {
            unpack(X[j], ii, jj);
            if (minim > v[ii][jj]) {
                minim = v[ii][jj];
                p = j;
            }
        }
        rp = rad(X[p]);
        unpack(rp, ip, jp);
        for (j = 1; j <= k; ++j)
            if (j != p) {
                rj = rad(X[j]);
                if (rj!=rp) {
                    unpack(rj, ij, jj);
                    v[ip][jp] += v[ij][jj];
                    v[ij][jj] = rp;
                }
            }
        if (-v[ip][jp] > maxim)
            maxim = -v[ip][jp];
        Y[++y] = maxim;
    }
    for (i= n * n - 1; i >= 0; --i) {
        fout << Y[i] << "\n";
    }
    return 0;
}