/**
 * @author n685
 * @date 2024-12-28 19:20:21
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 1e5;
// constexpr int N = 2;

struct Tree {
  static constexpr int LG = std::bit_width<u32>(N - 1);
  int n;
  const std::vector<std::vector<int>>& adj;
  std::vector<int> p, d, sub;
  std::vector<std::vector<int>> lift;
  std::vector<int> tl, tr;
  void dfs(int node, int par, int& cnt) {
    tl[node] = cnt++;
    p[node] = par;
    for (int i : adj[node]) {
      if (i == par) {
        continue;
      }
      d[i] = d[node] + 1;
      dfs(i, node, cnt);
      sub[node] += sub[i];
    }
    tr[node] = cnt - 1;
  }
  explicit Tree(const std::vector<std::vector<int>>& adj_)
      : n(static_cast<int>(adj_.size())),
        adj(adj_),
        p(n, -1),
        d(n),
        sub(n, 1),
        lift(LG, std::vector<int>(n, -1)),
        tl(n),
        tr(n) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (p[i] == -1) {
        dfs(i, -1, cnt);
      }
    }
    lift[0] = p;
    for (int i = 1; i < LG; ++i) {
      for (int j = 0; j < n; ++j) {
        if (lift[i - 1][j] != -1) {
          lift[i][j] = lift[i - 1][lift[i - 1][j]];
        }
      }
    }
  }
  int up(int u, int dist) const {
    if (dist < 0) {
      return -1;
    }
    if (d[u] < dist) {
      return -1;
    }
    for (int i = 0; i < LG; ++i) {
      if (((1 << i) & dist) != 0) {
        u = lift[i][u];
      }
    }
    return u;
  }
  // is v an ancestor of u?
  bool ancestor(int u, int v) const { return tl[u] <= tl[v] && tl[v] <= tr[u]; }

  int lca(int u, int v) const {
    if (d[u] < d[v]) {
      std::swap(u, v);
    }
    if (ancestor(v, u)) {
      return v;
    }
    for (int i = LG - 1; i >= 0; --i) {
      if (d[u] >= (1 << i) && !ancestor(lift[i][u], v)) {
        u = lift[i][u];
      }
    }
    return p[u];
  }
  int dist(int u, int v) const { return d[u] + d[v] - 2 * d[lca(u, v)]; }
};

struct DSU {
  std::vector<int> val;
  int cnt{};
  DSU() = default;
  explicit DSU(int n) : val(n, -1), cnt(n) {}
  int find(int i) { return val[i] < 0 ? i : (val[i] = find(val[i])); }
  bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) {
      return false;
    }
    if (val[u] > val[v]) {
      std::swap(u, v);
    }
    val[u] += val[v];
    val[v] = u;
    --cnt;
    return true;
  }
  bool connected(int u, int v) { return find(u) == find(v); }
  int size(int u) { return -val[find(u)]; }
  int count() const { return cnt; }
};

template <class T> std::array<T, 2> conv(const std::pair<T, T>& p) {
  return {p.first, p.second};
}
bool det(int u, int v, int dist) {
  if (u < N && v < N) {
    return dist % 4 == 2;
  }
  if (u >= N && v >= N) {
    return dist % 4 == 0;
  }
  return dist % 4 == 1;
}

std::array<int, 2> stay{N, N};
struct DSU2 {
  const Tree& tr;
  std::vector<int> val, dist;
  std::vector<std::array<int, 2>> ep;
  int cnt{};
  explicit DSU2(const Tree& tr_)
      : tr(tr_),
        val(tr.n, -1),
        dist(tr.n),
        ep(tr.n),
        cnt(tr.n) {
    for (int i = 0; i < tr.n; ++i) {
      ep[i] = {i, i};
    }
  }
  int find(int i) { return val[i] < 0 ? i : (val[i] = find(val[i])); }
  bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) {
      return false;
    }
    if (val[u] > val[v]) {
      std::swap(u, v);
    }
    val[u] += val[v];
    val[v] = u;
    if (ep[u][0] != -1) {
      --stay[det(ep[u][0], ep[u][1], dist[u])];
    }
    if (ep[v][0] != -1) {
      --stay[det(ep[v][0], ep[v][1], dist[v])];
    }
    if (ep[u][0] != -1 && ep[v][0] != -1) {
      std::array<int, 2> nv = ep[u];
      if (dist[u] < dist[v]) {
        dist[u] = dist[v];
        nv = ep[v];
      }
      for (int i : ep[u]) {
        for (int j : ep[v]) {
          int cd = tr.dist(i, j);
          if (dist[u] < cd) {
            dist[u] = cd;
            nv = {i, j};
          }
        }
      }
      ep[u] = nv;
      ++stay[det(ep[u][0], ep[u][1], dist[u])];
    }
    --cnt;
    return true;
  }
  bool connected(int u, int v) { return find(u) == find(v); }
  int size(int u) { return -val[find(u)]; }
  int count() const { return cnt; }
};

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int q;
  std::cin >> q;

  DSU dsu(2 * N);
  std::vector<std::vector<int>> adj(2 * N);
  std::vector<int> a(q), b(q);
  for (int i = 0; i < q; ++i) {
    std::cin >> a[i] >> b[i];
    --a[i];
    b[i] += N - 1;
    if (dsu.unite(a[i], b[i])) {
      adj[a[i]].push_back(b[i]);
      adj[b[i]].push_back(a[i]);
    }
  }
  Tree tr(adj);

  DSU2 dsu2(tr);
  std::vector<bool> cy(2 * N);
  for (int i = 0; i < q; ++i) {
    if (!dsu2.unite(a[i], b[i])) {
      int rt = dsu2.find(a[i]);
      if (dsu2.ep[rt][0] != -1) {
        --stay[det(dsu2.ep[rt][0], dsu2.ep[rt][1], dsu2.dist[rt])];
      }
      dsu2.ep[rt] = {-1, -1};
      int u = a[i], v = b[i];
      int l = tr.lca(u, v);
      while (u != l && !cy[u]) {
        cy[u] = true;
        ++stay[u >= N];
        u = tr.p[u];
      }
      if (!cy[l]) {
        cy[l] = true;
        ++stay[l >= N];
      }
      while (v != l && !cy[v]) {
        cy[v] = true;
        ++stay[v >= N];
        v = tr.p[v];
      }
    }
    std::cout << N - stay[0] << ' ' << N - stay[1] << '\n';
  }
}