# include <bits/stdc++.h>
using namespace std;
const int N=1e5;
int bad1,bad2,bad3,ffa[200010],U[200010],V[200010],len[200010],minn[20][200010],fa[200010],dfn[200010],idfn[200010],dep[200010],a[1000010],b[1000010],tot;
bool vis[200010],good[200010],bad[200010],del[200010],isroot[200010];
set<pair<int,int>> st2;
vector<int> G[200010];
int getF(int x){return ffa[x]==x?x:ffa[x]=getF(ffa[x]);}
int Low(int u,int v){return dep[u]<dep[v]?u:v;}
int lca(int u,int v)
{
	if(u==v) return u;
	u=dfn[u];v=dfn[v];
	if(u>v) swap(u,v);
	int k=__lg(v-u);
	return fa[Low(minn[k][u+1],minn[k][v-(1<<k)+1])];
}
int dis(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
void dfs(int u)
{
	dfn[u]=++tot;minn[0][tot]=u;
	for(int v:G[u])
	{
		if(v==fa[u]) continue;
		fa[v]=u;dep[v]=dep[u]+1;
		dfs(v);
	}
}
void Del(int u)
{
	for(;u && !del[u];u=fa[u])
	{
		del[u]=1;
		(u<=N?bad1:bad2)++;
	}
}
bool badvertex(int x)
{
	if((U[x]<=N)!=(V[x]<=N))
	{
		if(len[x]%4==1) return 1;
		else return 0;
	}
	else
	{
		if(len[x]%4==0) return U[x]>N;
		else return U[x]<=N;
	}
}
void merge(int u,int v)
{
	int x=getF(u),y=getF(v);
	if(x==y)
	{
		if(!bad[x]) (badvertex(x)?bad2:bad1)--;
		bad[x]=1;
		Del(u);Del(v);
		return;
	}
	if(!bad[x] && !bad[y])
	{
		(badvertex(x)?bad2:bad1)--;
		(badvertex(y)?bad2:bad1)--;
		int v1[]={U[x],V[x]},v2[]={U[y],V[y]},p1=U[x],p2=V[x],t,mx=len[x];
		if(mx<len[y]) mx=len[y],p1=U[y],p2=V[y];
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				if((t=dis(v1[i],v2[j]))>mx)
					mx=t,p1=v1[i],p2=v2[j];
		U[x]=p1;V[x]=p2;len[x]=mx;
		(badvertex(x)?bad2:bad1)++;
	}
	else if(!bad[x]) (badvertex(x)?bad2:bad1)--;
	else if(!bad[y]) (badvertex(y)?bad2:bad1)--;
	else Del(u),Del(v);
	bad[x]=(bad[x] || bad[y]);ffa[y]=x;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int q;
	cin>>q;
	iota(ffa+1,ffa+2*N+1,1);
	for(int i=1;i<=q;i++) cin>>a[i]>>b[i];
	for(int i=1;i<=q;i++)
	{
		if(st2.count({a[i],b[i]})) continue;
		st2.emplace(a[i],b[i]);
		good[i]=1;
		int x=getF(a[i]),y=getF(b[i]+N);
		if(x==y)
		{
			if(!bad[x])
			{
				bad[x]=1;
				isroot[a[i]]=1;
			}
		}
		else if(!bad[y] || !bad[x])
		{
			ffa[y]=x;bad[x]=(bad[x] || bad[y]);
			G[a[i]].push_back(b[i]+N);
			G[b[i]+N].push_back(a[i]);
		}
	}
	for(int i=1;i<=2*N;i++)
		if(!bad[i] && i==ffa[i]) isroot[i]=1;
	for(int i=1;i<=2*N;i++)
		if(!dfn[i] && isroot[i]) dfs(i);
	for(int i=1;i<=17;i++)
		for(int j=1;j+(1<<i)-1<=tot;j++)
			minn[i][j]=Low(minn[i-1][j],minn[i-1][j+(1<<(i-1))]);
	iota(ffa+1,ffa+2*N+1,1);
	for(int i=1;i<=2*N;i++) U[i]=V[i]=i,bad[i]=0;
	bad1=bad2=N;
	for(int i=1;i<=q;i++)
	{
		int u=a[i],v=b[i]+N;
		if(good[i]) merge(u,v);
		cout<<N-bad1<<" "<<N-bad2<<"\n";
	}
	return 0;
}