记录编号	134590	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2014-10-30 15:36:34	内存使用	2.69 MiB

/*
	Name:1439. [NOIP2013]货车运输
	Author:hzoi-jsx
	Date:30/10/14 15:38
	Description: 倍增
*/
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

int N=0,M=0,r1=0,r2=0,Q=0,Deep;
int F[10010]={0},D[10010]={0};
inline int find(int x){
	if(F[x]!=x) F[x]=find(F[x]);
	return F[x];
}
inline bool Union(int x,int y){
    r1=find(x); r2=find(y);
    if(r1==r2) return false;
    else{
        F[r2]=r1; return true;
	}
}

inline int Getint() {
	int ret,neg;	char ch;
	ret = neg = 0 ; while (!isdigit(ch=getchar())&&ch!='-') ;
	if (ch=='-') neg = 1 , ch=getchar() ;
	while (ret = ret*10+ch-'0' , isdigit(ch=getchar())) ;
	if (neg) ret = -ret ;
	return ret ;
}

class node{
	public:
		int s,t,v;
		bool operator < (const node& b) const {
			return v>=b.v;
		}
}E[50010];

class data{
	public:
		int to,next,v;
}T[30010];
int line[30010]={0},tot=0;
inline void Insert(int x,int y,int v){
   tot++; T[tot].to=y; T[tot].v=v; T[tot].next=line[x]; line[x]=tot;
}
int W[10010][17]={0},Fa[10010][17]={0};
void Build(int x,int deep){
	D[x]=deep;
	for(int i=line[x];i!=0;i=T[i].next){
		int p=T[i].to;
		if(!Fa[p][0]){
			Fa[p][0]=x; W[p][0]=T[i].v; Build(p,deep+1);
		}
	}
}

int LCA(int x,int y){
	int Res=INT_MAX;
	if(D[x]<D[y]) swap(x,y);
	for(int j=Deep-1;j>=0;--j){
		if(D[Fa[x][j]]>=D[y]){
			Res=min(Res,W[x][j]); x=Fa[x][j];
		}
	}
	if(x!=y){
		for(int j=Deep-1;j>=0;--j){
			if(Fa[x][j]!=Fa[y][j]){
				Res=min(Res,min(W[x][j],W[y][j]));
				x=Fa[x][j]; y=Fa[y][j];
			}
		}
		Res=min(Res,min(W[x][0],W[y][0]));
	}
	return Res;
}

int main(){
    freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);

	N=Getint();M=Getint();
	Deep=(int)(log((double)N)/log(2.0))+1;

	for(int i=1;i<=M;++i){
		E[i].s=Getint(); E[i].t=Getint(); E[i].v=Getint();
	}
	sort(E+1,E+M+1);
	for(int i=1;i<=N;++i) F[i]=i;
	for(int i=1;i<=M;++i){
		if(Union(E[i].s,E[i].t)){
			Insert(E[i].s,E[i].t,E[i].v);
			Insert(E[i].t,E[i].s,E[i].v);
		}
	}
	for(int i=1;i<=N;++i){
		if(!Fa[i][0]){
			W[i][0]=INT_MAX; Fa[i][0]=i; Build(i,1);
		}
	}
	for(int j=1;j<Deep;++j){
		for(int i=1;i<=N;++i){
			Fa[i][j]=Fa[Fa[i][j-1]][j-1];
			W [i][j]=min(W[i][j-1],W[Fa[i][j-1]][j-1]);
		}
	}

	Q=Getint();
	int x=0,y=0;
	for(int i=1;i<=Q;++i){
		x=Getint();y=Getint();
		if(find(x)!=find(y)) puts("-1");
		else printf("%d\n",LCA(x,y));
	}
	return 0;
}