#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

const int MAX_N = 200000 + 5;
const int MAX_M = 1000000 + 5;

struct Graph{
    struct UnionFind{
        int fath[MAX_N];
        UnionFind () {
            for (int i = 1; i < MAX_N; i ++) fath[i] = i;
        }
        int Find(int x) {return x == fath[x] ? x : fath[x] = Find(fath[x]);}
        bool Merge(int a, int b) {
            int x = Find(a), y = Find(b);
            if (x == y) return false;
            fath[y] = x;
            return true;
        }
        int operator [] (int x) {return Find(x);}
        bool operator () (int a, int b) {return Merge(a, b);}
    }rt;
    char vis[MAX_N];
    int n, fa[MAX_N], dep[MAX_N], sz[MAX_N], bs[MAX_N], tp[MAX_N];
    int cnt[2], ans[MAX_M][2], diff[MAX_M][2];
    vector <int> edge[MAX_N];
    struct Node{
        int id, rt, u, v;
        Node (int id_ = 0, int rt_ = 0, int u_ = 0, int v_ = 0) : id(id_), rt(rt_), u(u_), v(v_) {}
    };
    vector <Node> qry[MAX_N];
    
    void dfs1(int u, int fath) {
        sz[u] = 1;
        bs[u] = 0;
        fa[u] = fath;
        dep[u] = dep[fath] + 1;
        for (auto v : edge[u]) {
            if (!(vis[v] & 2) && v != fath) {
                dfs1(v, u);
                sz[u] += sz[v];
                if (sz[bs[u]] < sz[v]) bs[u] = v;
            }
        }
    }
    
    void dfs2(int u, int gr) {
        tp[u] = gr;
        if (bs[u]) dfs2(bs[u], gr);
        for (auto v : edge[u]) {
            if (!(vis[v] & 2) && v != fa[u] && v != bs[u]) {
                dfs2(v, v);
            }
        }
    }
    
    int Lca(int u, int v) {
        while (tp[u] != tp[v]) {
            if (dep[tp[u]] < dep[tp[v]]) v = fa[tp[v]];
            else u = fa[tp[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    int calcDis(int u, int v) {
        return dep[u] + dep[v] - (dep[Lca(u, v)] << 1);
    }
    
    pii dfs3(int u, int fath, int dep) {
        pii res(dep, u);
        for (auto v : edge[u]) {
            if (v != fath && !(vis[v] & 2)) {
                res = max(res, dfs3(v, u, dep + 1));
            }
        }
        return res;
    }
    
    void maintain(int &diameter, int &u, int &v, int u1, int v1) {
        int u_ = u, v_ = v;
        int dis = calcDis(u1, v1);
        if (diameter < dis) {
            diameter = dis;
            u_ = u1; v_ = v1;
        }
        dis = calcDis(u, v1);
        if (diameter < dis) {
            diameter = dis;
            u_ = u; v_ = v1;
        }
        dis = calcDis(u1, v);
        if (diameter < dis) {
            diameter = dis;
            u_ = u1; v_ = v;
        }
        dis = calcDis(u, u1);
        if (diameter < dis) {
            diameter = dis;
            u_ = u; v_ = u1;
        }
        dis = calcDis(v, v1);
        if (diameter < dis) {
            diameter = dis;
            u_ = v; v_ = v1;
        }
        u = u_; v = v_;
    }
    
    pii rebuild(int root, int fath, int ti) {
        dfs1(root, fath);
        if (!ti) return pii(0, 0);
        dfs2(root, root);
        int root_ = rt[root];
        for (auto &[id, rt_, u, v] : qry[root_]) {
            if (rt_ != root_) vis[rt_] |= 2;
            else {
                assert(false);
            }
        }
        int u = dfs3(root, fath, 0).second;
        auto [diameter, v] = dfs3(u, 0, 0);
        char flag = 0;
        for (auto &[id, rt_, u1, v1] : qry[root_]) {
            if (rt_ != root_) {
                vis[rt_] &= ~2;
                if (flag) {
                    flag = 2;
                    diff[id][~ diameter >> 1 & 1] ++;
                }else {
                    flag = 1;
                }
                maintain(diameter, u, v, u1, v1);
                diff[id][~ diameter >> 1 & 1] --;
            }
        }
        qry[root_].clear();
        if (flag == 2) {
            diff[ti][~ diameter >> 1 & 1] ++;
        }
        return pair(u, v);
    }
    
    void erase(int x, int y, int id) {
        int root = rt[x];
        if (root != 1) {
            rebuild(root, 1, id);
        }
        int u = x, v = y;
        while (u != v) {
            if (dep[u] < dep[v]) {
                vis[v] |= 2;
                cnt[v & 1] --;
                v = fa[v];
            }else {
                vis[u] |= 2;
                cnt[u & 1] --;
                u = fa[u];
            }
        }
        if (u != 1) {
            vis[u] |= 2;
            cnt[u & 1] --;
        }
        if (root != 1) {
            for (auto v : edge[u]) {
                if (!(vis[v] & 2)) rebuild(v, 1, 0);
            }
            u = x; v = y;
            while (u != v) {
                if (dep[u] < dep[v]) {
                    for (auto w : edge[v]) {
                        if (!(vis[w] & 2)) rebuild(w, 1, 0);
                    }
                    v = fa[v];
                }else {
                    for (auto w : edge[u]) {
                        if (!(vis[w] & 2)) rebuild(w, 1, 0);
                    }
                    u = fa[u];
                }
            }
            return ;
        }
        v = u == 1 ? u : fa[u];
        while (v != 1) {
            vis[v] |= 2;
            cnt[v & 1] --;
            v = fa[v];
        }
        u = x; v = y;
        while (u != v) {
            if (dep[u] < dep[v]) {
                for (auto w : edge[v]) {
                    if (!(vis[w] & 2)) fa[w] = 1;
                }
                v = fa[v];
            }else {
                for (auto w : edge[u]) {
                    if (!(vis[w] & 2)) fa[w] = 1;
                }
                u = fa[u];
            }
        }
        while (u != 1) {
            for (auto w : edge[u]) {
                if (!(vis[w] & 2)) fa[w] = 1;
            }
            u = fa[u];
        }
    }
    
    void addEdge(int x, int y, int idx) {
        for (int &i = n; i < idx; i ++) {
            ans[i + 1][0] = cnt[0];
            ans[i + 1][1] = cnt[1];
        }
        assert(n == idx);
        assert((x & 1) ^ (y & 1));
        if (!vis[x]) {
            vis[x] = 1;
            cnt[x & 1] ++;
        }
        if (!vis[y]) {
            vis[y] = 1;
            cnt[y & 1] ++;
        }
        int fx = rt[x], fy = rt[y];
        if (fx == fy) {
            erase(x, y, idx);
        }else {
            edge[x].emplace_back(y);
            edge[y].emplace_back(x);
            if (fy == 1 || fx != 1 && sz[fx] < sz[fy]) {
                swap(x, y);
                swap(fx, fy);
            }
            auto [u, v] = rebuild(fy, 0, idx);
            rebuild(y, x, 0);
            if (fx != 1) {
                qry[fx].emplace_back(idx, y, u, v);
            }
            rt(fx, fy);
        }
        ans[idx][0] = cnt[0];
        ans[idx][1] = cnt[1];
    }
    
    void solve() {
        for (int i = 2; i < MAX_N; i ++) {
            if (vis[i] == 1 && rt[i] == i) rebuild(i, 0, n + 1);
        }
        for (int i = 1; i <= n; i ++) {
            diff[i][0] += diff[i - 1][0];
            diff[i][1] += diff[i - 1][1];
            ans[i][0] += diff[i][0];
            ans[i][1] += diff[i][1];
        }
    }
    
    pii operator [] (int id) const {
        return pair(ans[id][0], ans[id][1]);
    }
}G;
int N, cnt[MAX_N], redLeaves[MAX_N], rp[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for (int i = 1; i <= N; i ++) {
        int x, y;
        cin >> x >> y;
        x <<= 1; (y <<= 1) |= 1;
        redLeaves[i] = redLeaves[i - 1];
        if (!cnt[x]) {
            rp[x] = y;
            redLeaves[i] ++;
        }else {
            if (cnt[x] == 1) {
                G.addEdge(x, rp[x], i);
                redLeaves[i] --;
            }
            G.addEdge(x, y, i);
        }
        cnt[x] ++;
    }
    G.solve();
    for (int i = 1; i <= N; i ++) {
        auto [x, y] = G[i];
        cout << x + redLeaves[i] << ' ' << y << '\n';
    }
    
    return 0;
}