New Roads Queries

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4constexpr int LOG=20;
5
6namespace dsu{
7  vector<int> pa,sz;
8  int n;
9  void init(int _n){
10    n=_n;
11    pa=vector<int>(n); iota(pa.begin(),pa.end(),0);
12    sz=vector<int>(n,1);
13  }
14  int f(int x){ return pa[x]==x?x:pa[x]=f(pa[x]); }
15  bool m(int a,int b){
16    int fa=f(a),fb=f(b);
17    if(fa==fb) return 0;
18    if(sz[fa]<sz[fb]) swap(fa,fb);
19    pa[fb]=fa;
20    sz[fa]+=sz[fb];
21    return 1;
22  }
23};
24
25namespace mst{
26  vector<array<int,LOG>> pa,di;
27  vector<int> dep;
28  int n;
29  void init(int _n){
30    n=_n;
31    pa=vector<array<int,LOG>>(n);
32    di=vector<array<int,LOG>>(n);
33    dep=vector<int>(n,-1);
34    for(int i=0;i<n;++i){
35      pa[i].fill(-1);
36      di[i].fill(0);
37    }
38  }
39  void dfs(vector<vector<pair<int,int>>>& g,int root){
40    stack<int> st;
41    st.emplace(root);
42    while(st.size()){
43      int u=st.top(); st.pop();
44      for(auto&[w,v]:g[u]){
45        if(v==pa[u][0]) continue;
46        pa[v][0]=u;
47        di[v][0]=w;
48        dep[v]=dep[u]+1;
49        st.emplace(v);
50      }
51    }
52  }
53  void pa_init(){
54    for(int j=1;j<LOG;++j) for(int i=0;i<n;++i){
55      int p=pa[i][j-1];
56      pa[i][j]=pa[p][j-1];
57      di[i][j]=max(di[i][j-1],di[p][j-1]);
58    }
59  }
60  int lca(int a,int b){
61    if(pa[a][LOG-1]!=pa[b][LOG-1]) return -1;
62    if(dep[a]<dep[b]) swap(a,b);
63    int d=dep[a]-dep[b];
64    for(int i=0;i<LOG;++i) if(d>>i&1) a=pa[a][i];
65    if(a==b) return a;
66    for(int i=LOG-1;i>=0;--i) if(pa[a][i]!=pa[b][i]){
67      a=pa[a][i],b=pa[b][i];
68    }
69    return pa[a][0];
70  }
71  int dis(int l,int k){
72    int res=0;
73    for(int i=0;i<LOG;++i){
74      if(k>>i&1){
75        res=max(res,di[l][i]);
76        l=pa[l][i];
77      }
78    }
79    return res;
80  }
81  int qry(int a,int b){
82    int c=lca(a,b);
83    if(c==-1) return -1;
84    return max(dis(a,dep[a]-dep[c]),dis(b,dep[b]-dep[c]));
85  }
86};
87
88signed main(){
89  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
90
91  int n,m,q; cin>>n>>m>>q;
92
93  dsu::init(n);
94  vector<vector<pair<int,int>>> g(n);
95  for(int i=1;i<=m;++i){
96    int a,b; cin>>a>>b; --a,--b;
97    if(dsu::m(a,b)){
98      g[a].emplace_back(i,b);
99      g[b].emplace_back(i,a);
100    }
101  }
102
103  mst::init(n);
104  for(int i=0;i<n;++i){
105    if(mst::dep[i]==-1){
106      mst::pa[i][0]=i;
107      mst::di[i][0]=0;
108      mst::dep[i]=0;
109      mst::dfs(g,i);
110    }
111  }
112  mst::pa_init();
113
114  while(q--){
115    int a,b; cin>>a>>b; --a,--b;
116    cout<<mst::qry(a,b)<<'\n';
117  }
118  return 0;
119}