前几天刚学 \(\text{Kruskal}\) 重构树，用到 CF 里就不会了……
对于每个询问 \((l,r)\)，有以下两种情况：
-
\(l=r\)，此时显然答案为 0。
-
\(l<r\)。
对于第二种情况，可以构造一个函数 \(f(i)\) 为将点 \(i\) 和 \(i-1\) 两点连通的最小边数。换句话说，就是一组 \((i-1,i)\) 的询问。
于是现在，我们的 \(ans_{(l,r)}=\max_{i=l+1}^r f(i)\)。
于是我们就需要考虑 \(f(i)\) 怎么求。
可以发现，如果对第 \(i\) 条边赋一个边权 \(w=i\)，那么用 \(\text{Kruskal}\) 生成的最小生成树唯一且与原生成树相同。
于是边的编号转化为边的边权，现在 \(f(i)\) 变为求树上 \(i\) 和 \(i-1\) 路径上的最大边。
于是想到 \(\text{Kruskal}\) 重构树。
对原图加入边权后，跑出一颗 \(\text{Kruskal}\) 重构树，然后求 \(i\) 与 \(i-1\)
的 \(\text{lca}\) 的点权，就是 \(f(i)\)。
然后对于区间 \(\max\)，上一个 ST 表就能解决问题。
// Problem: E. Qpwoeirut and Vertices
// Contest: Codeforces Round #809 (Div. 2)
// URL: https://codeforces.com/contest/1706/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
ll x=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();
return x*f;
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
#define d rd()
#define pb push_back
ll qp(ll a,ll b,ll p){
ll ans=1;while(b){
if(b&1)ans=ans*a%p;
a=a*a%p;b>>=1;
}return ans;
}ll n,m,cnt,q;
vi e[200010];
ll val[200010];
struct node{ll u,v,w;}a[200010];
bool cmp(node a,node b){return a.w<b.w;}
ll fa[200010];
ll find(ll x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
ll f[200010][20];
ll de[200010];
ll st[200010][20];
ll lg[200010];
void dfs(ll u,ll fat){
f[u][0]=fat;
de[u]=de[fat]+1;
fe(i,e[u]){
ll v=e[u][i];
if(v==fat)continue;
dfs(v,u);
}
}ll lca(ll u,ll v){
if(de[u]<de[v])swap(u,v);
for(int i=19;i>=0;i--)
if(de[u]-(1<<i)>=de[v]){
u=f[u][i];
if(u==v)return u;
}
for(int i=19;i>=0;i--)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
int main(){
wt{
n=d,m=d,q=d;cnt=n;
f(i,1,n*2)e[i].clear(),fa[i]=i,de[i]=0;
f(i,1,m)a[i]={d,d,i};
sort(a+1,a+m+1,cmp);
f(i,1,m){
ll u=a[i].u,v=a[i].v,w=a[i].w;
if(find(u)==find(v))continue;
val[++cnt]=w;
u=find(u),v=find(v);
fa[u]=cnt,fa[v]=cnt;
e[cnt].pb(u),e[cnt].pb(v);
}
dfs(cnt,0);
f(j,1,19)f(i,1,cnt)f[i][j]=f[f[i][j-1]][j-1];
f(i,2,n)st[i][0]=val[lca(i,i-1)];
lg[0]=-1;f(i,1,n)lg[i]=lg[i/2]+1;
f(j,1,19)f(i,1,n)if(i+(1<<(j-1))<=n)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
while(q--){
ll l=d,r=d;
if(l==r){printf("0 ");continue;}
l++;
printf("%lld ",max(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]));
}puts("");
}
return 0;
}