https://www.luogu.com.cn/problem/P2245
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=3e5+5;
int n,m,q,fa[N][20][2],dep[N],v[N];
bool vis[N];
struct node
{
int x,y,w;
}a[M];
struct edge
{
int to,w;
};
vector<edge>e[N];
void dfs(int x,int father,int dis)
{
fa[x][0][0]=father;
fa[x][0][1]=dis;
dep[x]=dep[father]+1;
for(int i=1;i<=19;++i)
{
fa[x][i][0]=fa[fa[x][i-1][0]][i-1][0];
if(!fa[x][i][0]) continue;
fa[x][i][1]=max(fa[x][i-1][1],fa[fa[x][i-1][0]][i-1][1]);
}
for(auto i:e[x])
{
if(i.to==father) continue;
vis[i.to]=1;
dfs(i.to,x,i.w);
}
}
int f(int x)
{
if(v[x]!=x) v[x]=f(v[x]);
return v[x];
}
bool cmp(node x,node y)
{
return x.w<y.w;
}
void kruskal()
{
for(int i=1;i<=n;++i) v[i]=i;
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;++i)
{
int x=f(a[i].x);
int y=f(a[i].y);
if(x!=y)
{
v[x]=y;
e[a[i].x].push_back(edge{a[i].y,a[i].w});
e[a[i].y].push_back(edge{a[i].x,a[i].w});
}
}
}
int lca(int x,int y)
{
int ans=0;
if(f(x)!=f(y)) return -1;
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;--i)
if(dep[fa[x][i][0]]>=dep[y])
{
ans=max(ans,fa[x][i][1]);
x=fa[x][i][0];
}
if(x==y) return ans;
for(int i=19;i>=0;--i)
if(fa[x][i][0]!=fa[y][i][0])
{
ans=max(ans,fa[x][i][1]);
ans=max(ans,fa[y][i][1]);
x=fa[x][i][0];
y=fa[y][i][0];
}
ans=max(ans,fa[x][0][1]);
ans=max(ans,fa[y][0][1]);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
for(int i=1;i<=n;++i)
kruskal();
for(int i=1;i<=n;++i)
if(!vis[i])
{
vis[i]=1;
dfs(i,0,0);
}
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
int t=lca(x,y);
if(t==-1) printf("impossibl\n");
else printf("%d\n",t);
}
return 0;
}