#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
namespace io {
	const int __SIZE = (1 << 22) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool read (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void write (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::read; using io::write;

int n,_q;
int _u[1000005],_v[1000005];

int A[1000005],fa[1000005];//degree
struct node{
	int sum,rev,l,r,w,siz,fa;
}tree[1000005];
#define ls(rt) tree[rt].l
#define rs(rt) tree[rt].r
void pushup(int rt){
	tree[rt].sum = (A[rt] > 2) + tree[ls(rt)].sum + tree[rs(rt)].sum;
	tree[rt].siz = 1 + tree[ls(rt)].siz + tree[rs(rt)].siz;
}

inline void frp(int u){
	swap(ls(u),rs(u));
	tree[u].rev ^= 1;
}

void pushdown(int rt){
	if(!tree[rt].rev) return;
	if(ls(rt)) frp(ls(rt));
	if(rs(rt)) frp(rs(rt));
	tree[rt].rev = 0;
}

void ssplit(int rt,int k,int &x,int &y){
	if(!rt){
		x = y = 0;
		return;
	}
	pushdown(rt);
	if(tree[ls(rt)].siz + 1 <= k){
		x = rt;
		ssplit(rs(rt),k - tree[ls(rt)].siz - 1,rs(rt),y);
		if(rs(rt)) tree[rs(rt)].fa = rt;
	}else{
		y = rt;
		ssplit(ls(rt),k,x,ls(rt));
		if(ls(rt)) tree[ls(rt)].fa = rt;
	}
	pushup(rt);
}

void split(int rt,int k,int &x,int &y){
	ssplit(rt,k,x,y);
	if(x) tree[x].fa = 0;
	if(y) tree[y].fa = 0;
}

int MMerge(int x,int y){
	if(!x || !y) return x + y;

	if(tree[x].w < tree[y].w){
		pushdown(x);
		rs(x) = MMerge(rs(x),y);
		pushup(x);
		if(rs(x)) tree[rs(x)].fa = x;
		return x;
	}else{	
		pushdown(y);
		ls(y) = MMerge(x,ls(y));
		pushup(y);
		if(ls(y)) tree[ls(y)].fa = y;
		return y;
	}
}

int Merge(int x,int y){
	int z = MMerge(x,y);
	tree[z].fa = 0;
	return z;
}

int getrt(int u){
	while(tree[u].fa) u = tree[u].fa;
	return u;
}

int gettop(int u){
	while(tree[u].fa) u = tree[u].fa;
	while(1){
		pushdown(u);
		if(!ls(u)) return u;
		u = ls(u);
	}
}

int _sz;
int _stk[55];
int getrank(int u){
	int p = u;
	while(p){
		_stk[++_sz] = p;
		p = tree[p].fa;
	}
	while(_sz) pushdown(_stk[_sz--]);

	int ret = 1 + tree[ls(u)].siz;
	p = tree[u].fa;
	while(p){
		if(u == rs(p)) ret += 1 + tree[ls(p)].siz;
		u = p;
		p = tree[u].fa;
	}
	return ret;
}

void modify(int u){
	while(u){
		pushup(u);
		u = tree[u].fa;
	}
}

int ALL;
void dbg(){
	printf("dbg: ALL=%d\n",ALL);
	rep(u,1,n){
		printf("node %d fa on tree %d A=%d\n",u,fa[u],A[u]);
		printf("ls %d rs %d w %d fa %d rev %d sum %d siz %d\n",ls(u),rs(u),tree[u].w,tree[u].fa,tree[u].rev,tree[u].sum,tree[u].siz);
	}
	rep(u,1,n) if(fa[u]) printf("%d %d\n",u,fa[u]);
}

void modify(int u,int C){
	if(A[u] > 2) ALL--;
	A[u] += C;
	if(A[u] > 2) ALL++;
	modify(u);
}

void access(int u){
	int a,b,p,q,z,temp;
	temp = getrank(u);
	split(getrt(u),temp,a,b);
	if(b) fa[gettop(b)] = u;
	p = gettop(u);
	z = getrt(u);
	while(fa[p]){
		q = fa[p];
		temp = getrank(q);
		split(getrt(q),temp,a,b);
		if(b) fa[gettop(b)] = q;
		fa[p] = 0;
		z = Merge(a,z);
		p = gettop(z);
	}
}

void changeroot(int u){
	access(u);
	frp(getrt(u));
}

int _lnk;
int link(int u,int v){
	changeroot(u);changeroot(v);
	if(fa[gettop(u)] || gettop(u) == gettop(v)) return 0;
	fa[v] = u;
	_lnk = 1;
	return 1;
}

void cut(int u,int v){
	access(u);
	if(fa[v] == u){
		fa[v] = 0;
		return;
	}
	access(v);
	assert(fa[u] == v);
	fa[u] = 0;
}

int chainsum(int u,int v){
	changeroot(u);access(v);
	return tree[getrt(v)].sum;
}

mt19937 rnd(0);
int result[1000005][2];//有效区间
vector <pii> Q[1000005];
ll _result[1000005];

#undef ls
#undef rs
namespace SEG{
	struct node{
		int Mn,tag,rec,_tag;
		ll sum;
	}tree[4000005];
	#define ls (rt * 2)
	#define rs (rt * 2 + 1)
	void upd(int rt,int C){
		tree[rt].Mn += C;
		tree[rt].tag += C;
	}
	void _upd(int rt,int C){
		tree[rt].sum += 1ll * tree[rt].rec * C;
		tree[rt]._tag += C;
	}
	void pushup(int rt){
		tree[rt].sum = tree[ls].sum + tree[rs].sum;
		tree[rt].Mn = min(tree[ls].Mn,tree[rs].Mn);
		tree[rt].rec = 0;
		if(tree[ls].Mn == tree[rt].Mn) tree[rt].rec += tree[ls].rec;
		if(tree[rs].Mn == tree[rt].Mn) tree[rt].rec += tree[rs].rec;
	}
	void pushdown(int rt){
		upd(ls,tree[rt].tag);upd(rs,tree[rt].tag);
		if(tree[ls].Mn == tree[rt].Mn) _upd(ls,tree[rt]._tag);
		if(tree[rs].Mn == tree[rt].Mn) _upd(rs,tree[rt]._tag);
		tree[rt].tag = tree[rt]._tag = 0;
	}
	void build(int rt,int l,int r){
		tree[rt].rec = r - l + 1;
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void upload(int rt,int l,int r,int L,int R,int C){
		if(L > R) return;
		if(l == L && r == R){
			upd(rt,C);
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(rt);
		if(R <= mid){
			upload(ls,l,mid,L,R,C);
		}else if(L > mid){
			upload(rs,mid+1,r,L,R,C);
		}else{
			upload(ls,l,mid,L,mid,C);
			upload(rs,mid+1,r,mid+1,R,C);
		}
		pushup(rt);
	}
	void _upload(int rt,int l,int r,int L,int R){
		if(L > R) return;
		if(l == L && r == R){
			if(!tree[rt].Mn) _upd(rt,1);
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(rt);
		if(R <= mid){
			_upload(ls,l,mid,L,R);
		}else if(L > mid){
			_upload(rs,mid+1,r,L,R);
		}else{
			_upload(ls,l,mid,L,mid);
			_upload(rs,mid+1,r,mid+1,R);
		}
		pushup(rt);
	}
	ll query(int rt,int l,int r,int L,int R){
		if(l == L && r == R) return tree[rt].sum;
		int mid = (l + r) >> 1;
		pushdown(rt);
		if(R <= mid) return query(ls,l,mid,L,R);
		else if(L > mid) return query(rs,mid+1,r,L,R);
		else return query(ls,l,mid,L,mid) + query(rs,mid+1,r,mid+1,R);
	}
}
int occ[1000005];

int main(){
//	freopen("test.in","r",stdin);
	read(n);
	rep(i,1,n){
		read(_u[i]);
		read(_v[i]);
	}
	rep(u,1,n){
		tree[u].w = rnd();
		tree[u].siz = 1;
	}
	int p = 1,l = 1;
	rep(i,1,n){
		modify(_u[i],1);modify(_v[i],1);
		_lnk = 0;
		while(p < l && !link(_u[i],_v[i])){
			if(p != l - 1) cut(_u[p],_v[p]);

			modify(_u[p],-1);modify(_v[p],-1);
			p++;
		}

		if(!_lnk){
			while(!link(_u[i],_v[i])){
				cut(_u[l],_v[l]);
				l++;
			}
			rep(k,p,l - 2) link(_u[k],_v[k]);
		}
		while(p != l && chainsum(_u[l - 1],_v[l - 1]) != ALL){
			if(p != l - 1) cut(_u[p],_v[p]);
			modify(_u[p],-1);modify(_v[p],-1);
			p++;
		}

		result[i][0] = p;result[i][1] = l - 1;
	}

	read(_q);
	rep(i,1,_q){
		int pl,pr;
		read(pl);read(pr);
		Q[pr].eb(mkp(pl,i));
	}
	SEG::build(1,1,n);
	rep(i,1,n){
		SEG::upload(1,1,n,occ[_u[i]] + 1,i,1);
		SEG::upload(1,1,n,occ[_v[i]] + 1,i,1);
		SEG::upload(1,1,n,1,i,-1);
		SEG::_upload(1,1,n,result[i][0],result[i][1]);
		occ[_u[i]] = occ[_v[i]] = i;
		for(pii I:Q[i]) _result[I.second] = SEG::query(1,1,n,I.first,n);
	}
	rep(i,1,_q){
		write(result[i]);
		pc('\n');
	}
	return 0;
}

answer.code: In instantiation of ‘void io::write(I) [with I = int*]’:
answer.code:388:8:   required from here
answer.code:61:78: error: ordered comparison of pointer with integer zero (‘int*’ and ‘int’)
   61 |         template <class I> inline void write (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
      |                                                                            ~~^~~
answer.code:61:98: error: wrong type argument to unary minus
   61 |         template <class I> inline void write (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
      |                                                                                                  ^
answer.code:62:41: error: invalid operands of types ‘int*’ and ‘int’ to binary ‘operator%’
   62 |                 while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
      |                                       ~~^~~~
answer.code:62:56: error: invalid operands of types ‘int*’ and ‘int’ to binary ‘operator/’
   62 |                 while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
      |                                                      ~~^~~~~
answer.code:62:56: note:   in evaluation of ‘operator/=(int*, int)’