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

#define V vector
#define pb push_back
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
#define fi first
#define se second

typedef long long LL;
typedef pair<int, int> pi;

const int N = 2e5 + 100;

V<int> e[N];
int dep[N], f[N], sz[N], hs[N], top[N];
int l[N], r[N], id[N], tot;
void dfs1(int x, int p) {
    dep[x] = dep[p] + 1, f[x] = p, sz[x] = 1, hs[x] = -1;
    for(auto y : e[x]) {
        if(y == p) continue;
        dfs1(y, x);
        sz[x] += sz[y];
        if(hs[x] == -1 || sz[y] > sz[hs[x]]) hs[x] = y;
    }
}

void dfs2(int x, int t) {
    top[x] = t, l[x] = ++tot, id[l[x]] = x;
    if(hs[x] != -1) {
        dfs2(hs[x], t);
    }
    for(auto y : e[x]) {
        if(y == f[x] || y == hs[x]) continue;
        dfs2(y, y);
    }
    r[x] = tot;
}

void build(int n) {
    for(int i = 1; i <= n; i++) if(l[i] == 0) {
        dfs1(i, 0), dfs2(i, i);
    }
}

int LCA(int a, int b) {
    while(top[a] != top[b]) {
        if(dep[top[a]] > dep[top[b]]) a = f[top[a]];
        else b = f[top[b]];
    }
    return dep[a] > dep[b] ? b : a;
}
int dis(int a, int b) {
    int l = LCA(a, b);
    return dep[a] + dep[b] - dep[l] * 2 + 1;
}

int dsu_f[N], siz[N];
int par(int x) {
    if(x == dsu_f[x]) return x;
    return dsu_f[x] = par(dsu_f[x]);
}
void mer(int a, int b) {
    a = par(a), b = par(b);
    if(a == b) return;
    dsu_f[a] = b;
    siz[b] += siz[a];
}
void ini(int n) {
    for(int i = 1; i <= n; i++) dsu_f[i] = i, siz[i] = 1;
}

void solve() {
    int n = 1e5;
    int q; cin >> q;
    V<pi> op(q + 1);
    V<bool> tree_edge(q + 1);
    ini(n * 2);
    for(int i = 1; i <= q; i++) {
        cin >> op[i].fi >> op[i].se;
        int x = op[i].fi, y = op[i].se + n;
        if(par(x) != par(y)) mer(x, y), e[x].pb(y), e[y].pb(x), tree_edge[i] = 1;
    }
    build(n * 2);
    ini(n * 2);
    int x = n, y = n;
    auto apply_tree = [&](int u, int v, int t, bool hav_cyc) {
        // cout << "apptree : " << u << " " << v << " " << t << " " << hav_cyc << " " << x << " " << y << endl;
        if(hav_cyc) return;
        int cu = u <= n;
        int cv = v <= n;

        int d = dis(u, v);
        if(cv != cu) {
            if(d % 4 == 2) y -= t;
            else x -= t;
            return;
        }

        if(d % 4 == 3) cv ^= 1;
        if(cv == 1) x -= t;
        else y -= t;
    };
    auto get_n_d = [&](pi a, pi b) -> pi {
        array<int, 4> cur;
        cur[0] = a.fi, cur[1] = a.se, cur[2] = b.fi, cur[3] = b.se;
        int d = -1;
        int u, v;
        for(int i = 0; i <= 3; i++) {
            for(int j = i + 1; j <= 3; j++) {
                if(dis(cur[i], cur[j]) > d) u = cur[i], v = cur[j], d = dis(cur[i], cur[j]);
            }
        }
        return {u, v};
    };
    V<pi> d(2 * n + 1);
    V<V<int>> hav(2 * n + 1);
    V<bool> hav_cyc(2 * n + 1);
    V<int> bel(2 * n + 1);
    for(int i = 1; i <= n * 2; i++) {
        bel[i] = i;
        hav[i].pb(i);
        d[i] = {i, i};
        apply_tree(i, i, 1, 0);
    }
    auto tree_mer = [&](int x, int y) -> void {
        apply_tree(d[x].fi, d[x].se, -1, hav_cyc[x]);
        apply_tree(d[y].fi, d[y].se, -1, hav_cyc[y]);

        if(hav[y].size() < hav[x].size()) swap(x, y);
        if(hav_cyc[y]) hav_cyc[x] = 1;

        d[x] = get_n_d(d[x], d[y]);
        for(auto t : hav[y]) {
            hav[x].pb(t);
            bel[t] = x;
        }

        apply_tree(d[x].fi, d[x].se, 1, hav_cyc[x]);
    };

    V<int> vis(n * 2 + 1);
    auto kill = [&](int u, int l) -> void {
        u = par(u);
        while(dep[u] >= dep[l]) {
            // assert(u != 0);
            // cout << u << endl;
            assert(vis[u] == 0);
            vis[u] = 1;
            mer(u, f[u]);
            if(u <= n) x--;
            else y--;
            u = par(u);
        }
    };

    // cout << x << " " << y << endl;
    
    for(int i = 1; i <= q; i++) {
        auto [u, v] = op[i];
        v += n;
        if(tree_edge[i]) {
            // cout << "tree" << i << endl;
            tree_mer(bel[u], bel[v]);
        } else {
            // cout << "d : " << d[u].fi << " " << d[u].se << "\n";
            apply_tree(d[u].fi, d[u].se, -1, hav_cyc[bel[u]]);
            // cout << "x, y : " << x << " " << y << "\n";
            hav_cyc[bel[u]] = 1;
            apply_tree(d[u].fi, d[u].se, 1, hav_cyc[bel[u]]);
            // cout << "x, y : " << x << " " << y << "\n";

            int l = LCA(u, v);
            kill(u, l), kill(v, l);
        }
        // for(int i = 1; i <= 2 * n; i++) cout << vis[i] << " ";
        // cout << "\n";
        cout << x << " " << y << "\n";
        // cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    // int t; cin >> t;
    // while(t--)
        solve();
}