$Kruskal+倍增Lca+线段树$

$顺便问个问题，T ~ 1000，n,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];

template <typename T> inline void read(T &x) {
   char c=getchar();x=0;int f=0;
   for(;!isdigit(c);c=getchar()) f|=(c=='-');
   for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
   x=f?-x:x;
}
template <typename T> inline void write(T x) {
   if(x<0) putchar('-'), x=-x;
   if(x>9) write(x/10);
   putchar(x%10^48);
}

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 void 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() {
   
   read(T);
   for(int t=1;t<=T;++t) {
   	memset(E, 0, sizeof(E));
   	memset(d, 0, sizeof(d));
   	memset(dep, 0, sizeof(dep));
   	
   	read(n);read(m);read(q);
   	for(int i=1;i<=n;++i) faa[i] = i;
   	for(int i=1;i<=m;++i) {
   		read(E[i].u);read(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) {
   		read(x);read(y);
   		write(d[ st.qry(x, y, 1) ]);
   		putchar(' ');
   	}
   	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
-----

*/