【模板】最小割树(Gomory-Hu Tree)

题目背景

模板题。做本题之前请确保你会 Dinic 或 ISAP。如果你乱搞过了我请你抽烟。 根据惯例,网络流题不允许卡 Dinic/ISAP,但可以卡 EK,本题数据严格遵循上述条约。

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图,多次询问两点之间的最小割。 两点间的最小割是这样定义的:原图的每条边有一个割断它的代价,你需要用最小的代价使得这两个点不连通。

输入输出格式

输入格式


第一行两个数 $n,m$。 接下来 $m$ 行,每行 $3$ 个数 $u,v,w$,表示有一条连接 $u$ 与 $v$ 的无向边,割断它的代价为 $w$。 接下来这一行有一个整数$Q$,表示询问次数 接下来 $Q$ 行,每行两个数 $u,v$,你需要求出 $u$ 与 $v$ 之间的最小割 **注意:因为数据有误,给定图的真实点数应该是 $n+1$ 个,编号为 $0$ 到 $n$。**

输出格式


输出共 $Q$ 行,每行一个整数对应询问的答案

输入输出样例

输入样例 #1

4 5
1 2 2
2 3 2
4 2 3
4 3 1
1 3 1
3
1 4
2 4
2 3

输出样例 #1

3
4
4

说明

$1\le n\leq 500,\quad 0\le m\leq 1500,\quad 0\le Q\leq 10^5,\quad 0\leq w\leq 10^4,\quad u\neq v$