记录编号	138551	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.054 s
提交时间	2014-11-05 23:41:16	内存使用	1.63 MiB

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
#include <list>
typedef long long LL;
using namespace std;
#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("truck.in", "r");
FILE *out = fopen("truck.out", "w");
#endif
inline void getd(int &x){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
}
#define pb push_back
#define iter(v) v::iterator
/*=====================================*/
const int maxn = 10000 + 3, maxm = 50000 + 3, maxq = 30000 + 3;
int n, m, q;

struct edge{
	int a, b, w;
	bool operator < (const edge &b)const{
		return w > b.w;
	}
}E[maxm];

struct Query{
	int a, b, lca;
}qu[maxq];
list<int> Q_on[maxn];//Query on i
vector<int> T_p[maxn];//MST
int Root[maxn], Rcnt = 0, Pre[maxn], PreW[maxn];
bool dfs_ed[maxn] = {0};

struct UFS{
	int pre[maxn];
	void init(){
		for(int i = 1;i <= n;++i)
			pre[i] = i;
	}
	int inS(int a){return pre[a] == a ? a : pre[a] = inS(pre[a]);}
	void Union(int a, int b){//link a to b
		pre[inS(a)] = inS(b);
	}
}ufs, ufs2;

inline int otherp(int i, int a){return a ^ E[i].a ^ E[i].b;}
inline int otherq(int i, int a){return a ^ qu[i].a ^ qu[i].b;}

inline void init(){
	getd(n), getd(m);
	int i, a, b;
	for(i = 0;i < m;++i)
		getd(E[i].a), getd(E[i].b), getd(E[i].w);
	sort(E, E + m);
	getd(q);
	for(i = 0;i < q;++i){
		getd(a), getd(b);
		qu[i].a = a, qu[i].b = b;
		Q_on[a].pb(i);
		Q_on[b].pb(i);
	}
	ufs.init(); ufs2.init();
	for(i = 0;i < m;++i){
		a = ufs.inS(E[i].a), b = ufs.inS(E[i].b);
		if(a == b)continue;
		T_p[E[i].a].pb(i), T_p[E[i].b].pb(i);
		ufs.Union(a, b);
	}
}

void dfs(int R){
	dfs_ed[R] = 1;
	iter(vector<int>) it;
	int oth;
	for(it = T_p[R].begin();it != T_p[R].end();++it){
		oth = otherp(*it, R);
		if(oth == Pre[R]) continue;
		Pre[oth] = R;
		PreW[oth] = E[*it].w;
		dfs(oth);
	}
}

bool vis[maxn] = {0};
void Tarjan(int R){
	iter(vector<int>) it;
	iter(list<int>) it_l;
	int oth;
	for(it = T_p[R].begin();it != T_p[R].end();++it){
		oth = otherp(*it, R);
		if(oth == Pre[R])continue;
		Tarjan(oth);
		ufs2.Union(oth, R);
	}
	vis[R] = 1;
	for(it_l = Q_on[R].begin();it_l != Q_on[R].end();){
		oth = otherq(*it_l, R);
		if(vis[oth]){
			qu[*it_l].lca = ufs2.inS(oth);
			it_l = Q_on[R].erase(it_l);
		}
		else ++it_l;
	}
}

inline void ans(){
	int i, j, a, b, lca, Min;
	for(i = 0;i < q;++i){
		a = qu[i].a, b = qu[i].b, lca = qu[i].lca;
		if(ufs.inS(a) != ufs.inS(b)){
			fprintf(out, "-1\n");
			continue;
		}
		Min = 0x7fffffff;
		j = a;
		while(j != lca){
			if(Min > PreW[j])Min = PreW[j];
			j = Pre[j];
		}
		j = b;
		while(j != lca){
			if(Min > PreW[j])Min = PreW[j];
			j = Pre[j];
		}
		fprintf(out, "%d\n", Min);
	}
}

int main(){
	
	init();
	int i;
	for(i = 1;i <= n;++i)if(!dfs_ed[i]){
		Root[Rcnt++] = i;Pre[i] = i;PreW[i] = 0;
		dfs(i);
	}
	for(i = 0;i < Rcnt;++i)
		Tarjan(Root[i]);
	
	ans();
	
	return 0;
}