A

如果图是一棵树，那么可以考虑离线点分治解决。

具体的，在每一个点处计算经过这个点的路径的距离，则对于每一个点，有一个深度，那么答案变为加入一个 $dep$ 和询问是否存在一个 $dep$ 满足 $DEP+dep<=x$ 。

可以直接记录dep的最小值，之后如果不经过分治中心，就划归为子问题，接下来考虑图的情况。

显然有一个跨过 $i$ 的返祖边就代表 $i$ 在一个简单环中，所以跨过每个点的返祖边的个数都 $\leq k$。

此时一个最短路要么经过树上路径的分治中心 $C$，要么经过 跨过 $C$ 的全部非树边的端点（不然到不了其他子树）。

于是对于每一个关键点，将 $dep_u$ 变为 $u$ 到关键点的最短路即可同理做完，对于以上的 $O(k)$ 个点计算答案即可。

#include <bits/stdc++.h>
using namespace std;
vector<int>g[100005],T[100005];
bool vis[100005];
void dfs(int u,int f){
    vis[u]=1;
    for(int v:g[u]){
        if(v==f)continue;
        if(!vis[v]){
            dfs(v,u);
            T[u].push_back(v);
            T[v].push_back(u);
        }
    }
}
int sz[100005],rt,all;
void findrt(int u,int f){
    sz[u]=1;
    int mx=0;
    for(int v:T[u]){
        if(v==f||vis[v])continue;
        findrt(v,u);
        sz[u]+=sz[v];
        mx=max(mx,sz[v]);
    }
    mx=max(mx,all-sz[u]);
    if(mx+mx<=all){
        rt=u;
    }
}
int bel[100005],ins[100005];
vector<int>P;
void divide(int u,int f,int tp,int typ){
    sz[u]=1;
    bel[u]=tp;
    ins[u]=typ;
    P.push_back(u);
    for(int v:T[u]){
        if(v==f||vis[v])continue;
        divide(v,u,f==0?v:tp,typ);
        sz[u]+=sz[v];
    }
}
int dis[100005];
void sou(int x,int typ){
    dis[0]=1e9;
    for(int u:P){
        dis[u]=1e9;
    }
    // memset(dis,0x3f,sizeof(dis));
    queue<int>q;
    q.push(x);
    dis[x]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            if(0==vis[v]&&ins[v]==typ&&dis[v]==dis[0]){
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
}
int ans[200005];
vector<tuple<int,int,int> >vec[100005];
void solve(int u,vector<tuple<int,int,int> >ve){
    P.clear();
    divide(u,0,u,u);
    vector<int>pnt;
    for(int v:P){
        if(v==u)continue;
        for(int w:g[v]){
            if(ins[w]==u&&w!=u)
                if(bel[v]!=bel[w]){
                    pnt.push_back(w);
                }
        }
    }
    pnt.push_back(u);
    for(int a:pnt){
        sou(a,u);
        int mnd=1e9;
        for(auto [tp,val,id]:ve){
            if(tp==1){
                mnd=min(mnd,dis[val]);
            }else{
                ans[id]=min(ans[id],dis[val]+mnd);
            }
        }
    }
    for(auto [tp,val,id]:ve){
        if(val!=u){
            vec[bel[val]].push_back({tp,val,id});
        }
    }
    vis[u]=1;
    for(int v:T[u]){
        if(vis[v])continue;
        all=sz[v];
        findrt(v,u);
        vector<tuple<int,int,int> >tmp=vec[v];
        vec[v].clear();
        solve(rt,tmp);
    }
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    vector<tuple<int,int,int> >ve;
    int q;;
    cin>>q;
    for(int i=1;i<=q;i++){
        int tp,val;
        cin>>tp>>val;
        ve.push_back({tp,val,i});
    }
    memset(ans,0x3f,sizeof(ans));
    memset(vis,0,sizeof(vis));
    all=n;
    findrt(1,0);
    solve(rt,ve);
    for(int i=1;i<=q;i++){
        if(ans[i]<1e9){
            cout<<ans[i]<<'\n';
        }
    }
}