E. Qpwoeirut and Vertices

E. Qpwoeirut and Vertices

题意

在1-m中找一个最小的k值，使得l-r的点是联通的

思路

kruskal重构树，将标号记为权值，然后建树

/*
kruskal重构树+线段树
*/

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;

int h[M],ne[M<<1],e[M<<1],tot;
void add(int from,int to) {
    e[++tot]=to; ne[tot]=h[from]; h[from]=tot;
}

int fa[M];
int find(int x) {
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}

int n,m,q,ncnt;

int num[M];
void merge(int x,int y,int wi) {
    num[++ncnt]=wi;
    fa[x]=fa[y]=fa[ncnt]=ncnt;//合并
    add(ncnt,x);
    add(ncnt,y);
}

int dep[M],f[M][21];
void dfs(int now,int Fa) {
    dep[now]=dep[Fa]+1;
    f[now][0]=Fa;
    for(int i=1;i<=20;i++)f[now][i]=f[f[now][i-1]][i-1];
    for(int i=h[now];i;i=ne[i])dfs(e[i],now);
}

int lca(int x,int y) {
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}

void reset() {
    for(int i=1;i<=ncnt;i++)h[i]=num[i]=0;
    tot=0;
}

struct node {
    int l,r,val;
}tr[M<<2];
#define ul u<<1
#define ur u<<1|1

void up(int u) {
    tr[u].val=lca(tr[ul].val,tr[ur].val);
}

void build(int u,int l,int r) {
    tr[u]={l,r};
    if(l==r) {
        tr[u].val=l;
        return ;
    }
    int mid=(l+r)/2;
    build(ul,l,mid);
    build(ur,mid+1,r);
    up(u);
}

int query(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].val;
    int mid=(tr[u].l+tr[u].r)/2;
    if(r<=mid)return query(ul,l,r);
    if(l>mid)return query(ur,l,r);
    return lca(query(ul,l,r),query(ur,l,r));
}


void solve() {
    cin>>n>>m>>q;
    ncnt=n;
    for(int i=0;i<=n;i++)fa[i]=i;
    for(int i=1,x,y;i<=m;i++) {
        cin>>x>>y;
        int fx=find(x),fy=find(y);
        if(fx!=fy)merge(fx,fy,i);
    }
    dfs(ncnt,0);
    build(1,1,n);
    while(q--) {
        int x,y;
        cin>>x>>y;
        cout<<num[query(1,x,y)]<<' ';
    }
    cout<<endl;
    reset();
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int TT;cin>>TT;
    while(TT--)solve();
    return 0;
}