$Kruskal+倍增Lca+线段树$

顺便问个问题，T ~ 1000，m,q ~ 2e5 ，这不会炸吗？

$隔壁的hack过了，50pts$

#include<iostream> // CF1706E Qpwoeirut and Vertices
#include<cstdio> // T1000 1e5 2e5
#include<cstring>
#include<vector>
#define N 100037

using namespace std;

int T, n, m, q;
int x, y;
int faa[2*N], fa[2*N][25];

struct pot{
	int u, v;
	int id;
}E[4*N];

inline int find(int x) {
	if(x == faa[x]) return x;
	else return faa[x] = find(faa[x]);
}

int cnt, d[2*N];
vector <int> e[2*N];
inline void solve() { // Kruskal
	cnt = n;
	for(int i=1;i<=n;++i) e[i].clear();
	int x, y;
	for(int i=1;i<=m;++i) {
		x = find(E[i].u);
		y = find(E[i].v);
		if(x ^ y) {
			d[++ cnt] = E[i].id;
			faa[x] = faa[y] = faa[cnt] = cnt;
			fa[x][0] = fa[y][0] = cnt;
			e[cnt].push_back(x);			
			e[cnt].push_back(y);
		}
	}
	for(int j=1;j<=19;++j)
		for(int i=1;i<=cnt;++i)
			fa[i][j] = fa[fa[i][j-1]][j-1];
}

int dep[2*N];
inline dfs(int u) {
	int v;
	for(int i=0;i<e[u].size();++i) {
		v = e[u][i];
		dep[v] = dep[u] + 1;
		dfs(v);
	}
}

inline int Lca(int x, int y) {
	int fx, fy;
	if(dep[x] > dep[y]) swap(x, y);
	
	if(dep[x] == dep[y]) goto L;
	
	for(int j=19;j>=0;--j) {
		fy = fa[y][j];
		if(fy == 0) continue;
		if(dep[x] <= dep[fy]) y = fy;
		if(dep[x] == dep[y]) break;
	}
	
	L:
	if(x == y) return x;
	for(int j=19;j>=0;--j) {
		fx = fa[x][j];
		fy = fa[y][j];
		if(fx == fy) continue;
		if(fx==0 || fy==0) continue;
		x = fx;
		y = fy;
	}
	return fa[x][0];
}

struct SGTree{
	#define lp p << 1
	#define rp ((p << 1) | 1)
	struct qot{
		int l, r;
		int dat;
	}tr[4*N];
	void build(int l, int r, int p) {
		tr[p].l = l;
		tr[p].r = r;
		if(l == r) {
			tr[p].dat = l;
			return ;
		}
		int mid = (l + r) >> 1;
		build(l, mid, lp);
		build(mid+1, r, rp);
		tr[p].dat = Lca(tr[lp].dat, tr[rp].dat);
	}
	inline int qry(int l, int r, int p) {
//		cout<<tr[p].l<<" "<<tr[p].r<<endl;
		if(l<=tr[p].l && tr[p].r<=r) return tr[p].dat;
		int trmid = (tr[p].l + tr[p].r) >> 1, val = -1;
		if(l <= trmid) val = qry(l, r, lp);
		if(r > trmid) val = val==-1 ? qry(l, r, rp) : Lca(val, qry(l, r, rp));
//		cout<<tr[p].l<<" "<<tr[p].r<<" "<<val<<endl;
		return val;
	}
}st;
int main() {
	
	scanf("%d", &T);
	for(int t=1;t<=T;++t) {
		memset(E, 0, sizeof(E));
		memset(d, 0, sizeof(d));
		memset(dep, 0, sizeof(dep));
		
		scanf("%d%d%d", &n, &m, &q);
		for(int i=1;i<=n;++i) faa[i] = i;
		for(int i=1;i<=m;++i) {
			scanf("%d%d", &E[i].u, &E[i].v);
			E[i].id = i;
		}
		
		solve();
		dep[cnt] = 1;
		dfs(cnt);
		
//		cout<<"Lca: "<<Lca(8, 10)<<endl;
//		cout<<"Fa: "<<fa[8][1]<<endl;
		
		st.build(1, cnt, 1);
//		int f = 1;
//		for(int p=1;p<=18;++p) {
//			cout<<st.tr[p].l<<" "<<st.tr[p].r<<" "<<st.tr[p].dat<<endl;
//		}
		
		for(int i=1;i<=q;++i) {
			scanf("%d%d", &x, &y);
			printf("%d ", d[ st.qry(x, y, 1) ]);
		}
		putchar('\n');
	}
	
	return 0;
}
/*

-----
3
2 1 2
1 2
1 1
1 2
5 5 5
1 2
1 3
2 4
3 4
3 5
1 4
3 4
2 2
2 5
3 5
3 2 1
1 3
2 3
1 3

0 1 
3 3 0 5 5 
2
-----

*/