#include <bits/stdc++.h>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;

const int N = 2e5 + 500;
const int OFF = 1e5 + 250;
const int LOG = 18;
const int INF = 0x3f3f3f3f;

vector<pii> t[N];
int par[N], m;
int qa[N], qb[N], los[N];
int arp[LOG][N], dep[N];

int pr(int x) {
	if(par[x] == x) return x;
	return par[x] = pr(par[x]);
}

void mrg(int x, int y) {
	par[pr(x)] = pr(y);
}

void dfs(int x, int lst) {
	dep[x] = dep[lst] + 1;
	arp[0][x] = lst;
	for(auto &[y, tme] : t[x]) {
		if(y != lst) dfs(y, x);
	}
}

int lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	for(int j = LOG - 1;j >= 0;j--)
		if(dep[x] - dep[y] >= (1 << j)) x = arp[j][x];
	if(x == y) return x;
	for(int j = LOG - 1;j >= 0;j--)
		if(arp[j][x] != arp[j][y])
			x = arp[j][x], y = arp[j][y];
	return arp[0][x];
}

int omca_dolje[N], omca_gore[N], smrt[N];
vi izb[N], ubac[N];
set < int > smrti[N];

void racunaj(int x, int lst) {
	for(int y : ubac[x]) smrti[x].insert(y);
	for(auto &[y, tme] : t[x]) {
		if(y == lst) continue;
		racunaj(y, x);
		if(smrti[x].size() < smrti[y].size()) 
			swap(smrti[x], smrti[y]);
		for(int z : smrti[y]) smrti[x].insert(z);
	}
	if(smrti[x].empty())
		smrt[x] = INF;
	else
		smrt[x] = *smrti[x].begin();
	for(int y : izb[x]) smrti[x].erase(y);
}

void racunaj_gore(int x, int lst) {
	for(int _ = 0;_ < 2;_++) {
		int dos = omca_gore[x];
		for(auto &[y, tme] : t[x]) {
			if(y == lst) continue;
			omca_gore[y] = min(omca_gore[y], max(tme, dos));
			dos = min(dos, max(tme, omca_dolje[y]));
			if(_ == 1) racunaj_gore(y, x);
		}
		reverse(t[x].begin(), t[x].end());
	}
}

void racunaj_dolje(int x, int lst) {
	omca_dolje[x] = smrt[x];
	omca_gore[x] = smrt[x];
	for(auto &[y, tme] : t[x]) {
		if(y == lst) continue;
		racunaj_dolje(y, x);
		omca_dolje[x] = min(omca_dolje[x], max(tme, omca_dolje[y]));
	}
}

int digni(int a, int k) {
	for(int j = 0;j < LOG;j++)
		if(k & (1 << j)) a = arp[j][a];
	return a;
}

int pomakni(int a, int b, int lc, int k) {
	if(dep[a] - dep[lc] >= k)
		return digni(a, k);
	return digni(b, (dep[a] + dep[b] - 2 * dep[lc]) - k);
}

int sol[N][2];
int cnt[N][2];
pair<int,pii> diam[N];
int cur_ans[2], pos[N], dobar[N];

pair<int,pii> dist(int a, int b) {
	return {dep[a] + dep[b] - 2 * dep[lca(a, b)], {a, b}};
}

void mrg2(int x, int y) {
	//printf("spajam %d - %d\n", x, y);

	int tko = (x > OFF);
	x = pr(x), y = pr(y);
	
	if(!dobar[x] && !dobar[y]) return; 	
	if(dep[x] > dep[y]) swap(x, y);
	
	if(x == y) {
		cur_ans[0] -= cnt[x][0] + pos[x];
		cur_ans[1] -= cnt[x][1] - pos[x];
		dobar[x] = 0;
		return;
	}	

	if(dobar[x]) {
		cur_ans[0] -= cnt[x][0] + pos[x];
		cur_ans[1] -= cnt[x][1] - pos[x];	
	}	
	if(dobar[y]) {
		cur_ans[0] -= cnt[y][0] + pos[y];
		cur_ans[1] -= cnt[y][1] - pos[y];	
	}
	
	dobar[x] = dobar[x] & dobar[y];
	par[y] = x;
	
	if(!dobar[x]) return;
	
	
	cnt[x][0] += cnt[y][0];
	cnt[x][1] += cnt[y][1];
	cnt[x][tko]++;
	
	vector<pair<int,pii>> v = {diam[x], diam[y], 
			dist(diam[x].Y.X, diam[y].Y.X),
			dist(diam[x].Y.X, diam[y].Y.Y),
			dist(diam[x].Y.Y, diam[y].Y.X),
			dist(diam[x].Y.Y, diam[y].Y.Y)
	};
	sort(v.rbegin(), v.rend());
	diam[x] = v[0];
	
	if(diam[x].Y.Y > OFF) swap(diam[x].Y.X, diam[x].Y.Y);
	
	//printf("diam : %d %d %d %d\n", diam[x].Y.X, lca(diam[x].Y.X, diam[x].Y.Y), diam[x].Y.Y, diam[x].X);
	int root = pomakni(diam[x].Y.X, diam[x].Y.Y, lca(diam[x].Y.X, diam[x].Y.Y), diam[x].X / 2);
	//printf("%d %d\n", dep[diam[x].Y.X], dep[diam[x].Y.Y]);
	//printf("root = %d\n", root);
	
	
	pos[x] = 0;
	if(dep[x] % 2 != dep[root] % 2) {
		if(root > OFF) {
			pos[x] = 1;
		} else {
			pos[x] = -1;
		}
	}
	//printf("pos[ %d ] = %d  : (%d %d)\n", x, pos[x], cnt[x][0], cnt[x][1]);
	cur_ans[0] += cnt[x][0] + pos[x];
	cur_ans[1] += cnt[x][1] - pos[x];
	//printf("		dobar[ %d ] = %d\n", x, dobar[x]);
	//printf("\n\n\n\n");
}

int main() {
	for(int i = 0;i < N;i++) par[i] = i;
	scanf("%d", &m);
	for(int i = 0;i < m;i++) {
		scanf("%d%d", qa + i, qb + i);
		qb[i] += OFF;
		if(pr(qa[i]) == pr(qb[i])) {
			los[i] = 1;
		} else {
			mrg(qa[i], qb[i]);
			t[qa[i]].PB({qb[i], i});
			t[qb[i]].PB({qa[i], i});	
		}
	}
	for(int i = 0;i < N;i++) {
		omca_dolje[i] = omca_gore[i] = INF;
		if(!dep[i]) dfs(i,i);
	}
	for(int j = 1;j < LOG;j++) {
		for(int i = 1;i < N;i++)
			arp[j][i] = arp[j - 1][arp[j - 1][i]];
	}
	for(int i = 0;i < m;i++) {
		if(!los[i]) continue;
		int lc = lca(qa[i], qb[i]);
		//printf("i : %d    %d -- %d -- %d\n", i, qa[i], lc, qb[i]);
		ubac[qa[i]].PB(i);
		ubac[qb[i]].PB(i);
		izb[lc].PB(i);
	}
	for(int i = 0;i < N;i++) {
		if(dep[i] - 1) continue;
		racunaj(i, i);
		racunaj_dolje(i, i);
		racunaj_gore(i, i);
	}
	
	//for(int i = 0;i < N;i++) {
	//	if(i % OFF > 0 && i % OFF < 3) {
	//		printf("%d   %d %d %d\n", i, smrt[i], omca_dolje[i], omca_gore[i]);
	//	}
	//}
	
	for(int i = 0;i < m;i++) {
		if(los[i]) continue;
		if(dep[qa[i]] < dep[qb[i]]) swap(qa[i], qb[i]);
		int kraj = max(omca_dolje[qa[i]], omca_gore[qb[i]]);
		//printf("kraj[ %d ] = %d\n", i, kraj);
		if(kraj <= i) continue; 
		int poc = max(min(omca_dolje[qa[i]], omca_gore[qb[i]]), i);
		if(poc < INF) {
			int odg = 0;
			if(omca_dolje[qa[i]] > omca_gore[qb[i]])
				odg = qb[i] > OFF;
			else 
				odg = qa[i] > OFF;
			//printf("i %d : (%d, %d)\n", i, poc, kraj);
			sol[poc][odg]++;
			if(kraj < INF) sol[kraj][odg]--;
		}
	}
	for(int i = 0;i < N;i++) {
		diam[i] = {0, {i, i}};
		par[i] = i;
		dobar[i] = 1;
	}
	for(int i = 1;i < m;i++) {
		sol[i][0] += sol[i - 1][0];
		sol[i][1] += sol[i - 1][1];
	}
	for(int i = 0;i < m;i++) {
		mrg2(qa[i], qb[i]);
		//printf("						(%d + %d) (%d + %d)\n", cur_ans[0], sol[i][0], cur_ans[1], sol[i][1]);
		printf("%d %d\n", cur_ans[0] + sol[i][0], cur_ans[1] + sol[i][1]);
	}
	return 0;	
}