#include<bits/stdc++.h>
using namespace std;

using ar3=array<int,3>;
const int N=1e5,Q=1e6,S=N*2,L=18;

int q;
int a[Q],b[Q];
int p[S];
vector<int>g[S];
int jj[S][L],dd[S];
int c[S],f[S];
ar3 di[S];
int ans[2];

int find(int i){
    return p[i]==i?i:p[i]=find(p[i]);
}
int lca(int i,int j){
    if(dd[i]<dd[j])swap(i,j);
    int d=dd[i]-dd[j];
    for(int l=0;l<L;l++)if(l>>d&1)i=jj[i][l];
    if(i==j)return i;
    for(int l=L-1;l>=0;l--)if(jj[i][l]!=jj[j][l])i=jj[i][l],j=jj[j][l];
    assert(jj[i][0]==jj[j][0]);
    return jj[i][0];
}
int dis(int i,int j){
    return dd[i]+dd[j]-2*dd[lca(i,j)];
}
ar3 operator+(ar3 a,ar3 b){
    ar3 c=a[2]>b[2]?a:b;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++){
        int u=a[i],v=b[j],d=dis(u,v);
        if(d>c[2])c={u,v,d};
    }
    return c;
}
bool bad(ar3 a){
    return ((a[2]&1)||a[0]>=N)^bool(a[2]&2);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>q;
    for(int i=0;i<q;i++)cin>>a[i]>>b[i],a[i]--,b[i]--;
    iota(p,p+S,0);
    for(int i=0;i<q;i++)if(find(a[i])!=find(N+b[i])){
        g[a[i]].push_back(N+b[i]);
        g[N+b[i]].push_back(a[i]);
        int u=find(a[i]),v=find(N+b[i]);
        p[u]=p[v]=u;
    }
    for(int i=0;i<S;i++){
        static bool v[S];
        if(!v[i]){
            auto dfs=[&](auto dfs,int i)->void{
                v[i]=1;
                for(int l=1;l<L;l++)jj[i][l]=jj[jj[i][l-1]][l-1];
                for(int j:g[i])if(jj[i][0]^j){
                    dd[j]=dd[i]+1;
                    jj[j][0]=i;
                    dfs(dfs,j);
                }
            };
            jj[i][0]=i;
            dd[i]=0;
            dfs(dfs,i);
        }
    }
    for(int i=0;i<S;i++)g[i].clear();
    iota(p,p+S,0);
    for(int i=0;i<q;i++){
        int u=a[i],v=N+b[i];
        if(!c[u])c[u]=1,di[u]={u,u,0};
        if(!c[v])c[v]=1,di[v]={v,v,0};
        auto dfs=[&](auto dfs,int i)->void{
            c[i]=2;
            for(int j:g[i])if(f[i]^j){
                f[j]=i;
                dfs(dfs,j);
            }
        };
        if(c[u]==1&&c[v]==1){
            int x=find(u),y=find(v);
            if(x==y){
                ans[bad(di[x])]++;
                f[u]=-1,dfs(dfs,u);
                while(~v)c[v]=3,ans[v>=N]--,v=f[v];
            }else{
                g[u].push_back(v);
                g[v].push_back(u);
                ans[bad(di[x])]++;
                ans[bad(di[y])]++;
                p[x]=p[y]=x;
                di[x]=di[x]+di[y];
                ans[bad(di[x])]--;
            }
        }else if(c[u]!=1&&c[v]!=1){
            for(int x:{u,v})
                while(c[x]!=3)c[x]=3,ans[x>=N]--,x=f[x];
        }else{
            if(c[u]!=1)swap(u,v);
            ans[bad(di[find(u)])]++;
            f[u]=v,dfs(dfs,u);
        }
        cout<<ans[0]<<' '<<ans[1]<<'\n';
    }
}