#include<bits/stdc++.h>
#define N 70000
using namespace std;
int k[N], s[N], n, a[N], b[N], sm=0;
int rs[N];
int find(int x){
	int r=x, y;
	while(x!=k[x])x=k[x];
	while(k[r]!=r){
		y=k[r];
		k[r]=x;
		r=y;
	}
	return x;
}
void unite(int a, int b){
	a=find(a);
	b=find(b);
	if(a==b)return;
	if(s[a]<s[b]) swap(a, b);
	s[a]+=s[b];
	k[b]=a;
	find(b);
	find(a);
	if(s[a]>sm)sm=s[a];
}
void unire(int a, int b){
	int x=n*(a-1)+b;
	s[x]=1;
	if(b>1 && s[x-1]) {
		unite(x, x-1);
	}
	if(a<n && s[x+n]) unite(x, x+n);
	if(b<n && s[x+1]) unite(x, x+1);
	if(a>1 && s[x-n]) unite(x, x-n);
	if(s[x]>sm)sm=s[x];
}
int main(){
	int x, y;
	freopen("bile.in", "r", stdin);
	freopen("bile.out", "w", stdout);
	scanf("%d", &n);
	int m=n*n;
	for(int i=1;i<=m;i++){
		scanf("%d%d", &a[i], &b[i]);
		s[i]=0;
		k[i]=i;
	}
	for(int i=m;i>=1;i--){
		rs[i]=sm;
		unire(a[i], b[i]);
	}
//	printf("%d", rs[1]);
	for(int i=1;i<=m;i++)printf("%d\n", rs[i]);
	return 0;
}