solve(0,n) 全 T，solve(1,n) 100 分。

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
struct network{
	ll ps,pt,h[505],dep[505],cur[505],tot;
	struct edge{
		ll v,nxt,c,f;
	}e[10005];
	void init()
	{
		memset(h,0,sizeof h);
		tot = 1;
	}
	void reset()
	{
		for(ll i = 1;i <= tot;i++)
			e[i].f = 0;
	}
	void addedge(ll u,ll v,ll w)
	{
		e[++tot] = {v,h[u],w,0},h[u] = tot;
		e[++tot] = {u,h[v],w,0},h[v] = tot;
	}
	bool bfs()
	{
		queue<ll> q;
		memset(dep,0,sizeof dep),dep[ps] = 1,q.push(ps);
		while(!q.empty())
		{
			ll u = q.front();q.pop();
			for(ll i = h[u];i;i = e[i].nxt)
				if(!dep[e[i].v] && e[i].c > e[i].f)
					dep[e[i].v] = dep[u] + 1,q.push(e[i].v);
		}
		return dep[pt];
	}
	ll dfs(ll u,ll f)
	{
		if(u == pt || !f)
			return f;
		ll ret = 0;
		for(ll &i = cur[u];i;i = e[i].nxt)
		{
			ll v = e[i].v,d;
			if(dep[v] == dep[u] + 1 && (d = dfs(v,min(f - ret,e[i].c - e[i].f))))
			{
				ret += d,e[i].f += d,e[i ^ 1].f -= d;
				if(ret == f)
					return ret;
			}
		}
		return ret;
	}
	ll maxflow()
	{
		ll ans = 0;
		while(bfs())
		{
			for(ll i = 1;i <= 504;i++)
				cur[i] = h[i];
			ans += dfs(ps,INF);
		}
		return ans;
	}
}G;
struct Edge{
	ll v,w;
};
vector<Edge> E[505];
void adde(ll u,ll v,ll w)
{
	E[u].push_back({v,w});
	E[v].push_back({u,w});
}
ll T,n,m,q,t[505],t1[505],t2[505];
void solve(ll l,ll r)
{
	if(l == r)
		return;
	G.reset(),G.ps = t[l],G.pt = t[r];
	ll v = G.maxflow(),p1 = 0,p2 = 0;
	adde(t[l],t[r],v);
	for(ll i = l;i <= r;i++)
		if(G.dep[t[i]])
			t1[++p1] = t[i];
		else
			t2[++p2] = t[i];
	for(ll i = 1;i <= p1;i++)
		t[l + i - 1] = t1[i];
	for(ll i = 1;i <= p2;i++)
		t[l + p1 + i - 1] = t2[i];
	solve(l,l + p1 - 1),solve(l + p1,r);
}
ll ans[505][505],tot;
void dfs(ll u,ll f,ll g,ll v)
{
	ans[u][g] = v;
	for(auto i : E[u])
		if(i.v != f)
			dfs(i.v,u,g,min(i.w,v));
}
int main()
{
	scanf("%lld%lld",&n,&m);
	G.init();
	for(ll i = 1;i <= m;i++)
	{
		ll u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		G.addedge(u,v,w);
	}
	for(ll i = 0;i <= n;i++)
		t[i] = i;
	solve(1,n);
	tot = 0;
	for(ll i = 1;i <= n;i++)
		dfs(i,0,i,INF);
	scanf("%lld",&q);
	for(ll i = 1;i <= q;i++)
	{
		ll u,v;
		scanf("%lld%lld",&u,&v);
		printf("%lld\n",ans[u][v]);
	}
	return 0;
}