P1967 WA10 求调

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct s{
	long long st,en;
	long long w;
};
s arr[1000005];
long long n,m,k;
long long a,b;
long long fa[1000005];
long long num[1000005],pre[1000005],wh[1000005],last[100005],cnt;
long long t[1000005];
long long dep[1000005];
long long roo[1000005][25],dis[1000005][25];
bool cmp(s x,s y){
	return x.w>y.w;
}
long long getfa(long long x){
	if(fa[x]==x){
		return x;
	}
	else{
		return fa[x]=getfa(fa[x]);
	}
}
void add(long long x,long long y,long long z){
	++cnt;
	num[cnt]=y;
	pre[cnt]=last[x];
	wh[cnt]=z;
	last[x]=cnt;
}
void klu(){
	sort(arr+1,arr+1+m,cmp);
	for(long long i=1;i<=n;i=-(~i)){
		fa[i]=i;
	}
	long long tmp=0;
	for(long long i=1;i<=m&&tmp<n-1;i=-(~i)){
		if(getfa(arr[i].st)==getfa(arr[i].en)){
			continue;
		}
		else{
			fa[fa[arr[i].st]]=fa[arr[i].en];
			add(arr[i].st,arr[i].en,arr[i].w);
			add(arr[i].en,arr[i].st,arr[i].w);
			tmp++;
		}
	}
}
void dfs(long long xy){
	t[xy]=1;
	for(long long i=last[xy];i;i=pre[i]){
		if(t[num[i]]==1){
			continue;
		}
		else{
			dep[num[i]]=dep[xy]+1;
			roo[num[i]][0]=xy;
			dis[num[i]][0]=wh[i];
			t[num[i]]=1;
			dfs(num[i]);
		}
	}
}
void mak(){
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=20;j++){
			roo[i][j]=roo[roo[i][j-1]][j-1];
			dis[i][j]=min(dis[i][j-1],dis[roo[i][j-1]][j-1]);
		}
	}
}
long long get(long long x,long long y){
	if(getfa(x)!=getfa(y)){
		return -1;
	}
	long long ans=0x3f3f3f3f3f;
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(long long i=20;i>=0;i--){
		if(dep[roo[x][i]]>=dep[y]){
			ans=min(ans,dis[x][i]);
			x=roo[x][i];			
		}
	}
	if(x==y){
		return ans;
	}
	else{
		for(long long i=20;i>=0;i--){
			if(roo[x][i]!=roo[y][i]){
				ans=min(ans,min(dis[x][i],dis[y][i]));
				x=roo[x][i];
				y=roo[y][i];
			}
		}
		return min(ans,min(dis[x][0],dis[y][0]));
	}
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=m;i=-(~i)){
		cin>>arr[i].st>>arr[i].en>>arr[i].w;
	}
	klu();
	for(long long i=1;i<=n;i++){
		if(t[i]==0){
			dep[i]=1;
			dfs(i);
			roo[i][0]=i;
			dis[i][0]=0x3f3f3f3f3f;
		}
	}
	mak();
	cin>>k;
	for(long long i=1;i<=k;i++){
		cin>>a>>b;
		printf("%lld\n",get(a,b));
	}
	return 0;
}