由于某些原因本题仅支持 C++ 各版本语言的提交。

印度尼西亚有 $N$ 个城市以及 $M$ 条双向道路，城市从 $0$ 到 $N −1$ 编号，道路从 $0$ 到 $M −1$ 编号。每条道路连接着两个不同的城市，第 $i$ 条道路连接第 $U[i]$ 个城市与第 $V [i]$ 个城市，汽车行驶这条道路将耗费 $W[i]$ 个单位汽油。通过这些道路，任意两个城市间能够互相到达。

接下来的 $Q$ 天中, 每天会有一对城市希望建立政治关系。具体来说，第 $j$ 天，第 $X[j]$ 个城市想要和第 $Y [j]$ 个城市建立政治关系。为此，第 $X[j]$ 个城市将会派一名代表坐汽车前往第 $Y [j]$ 个城市。同样地，第 $Y [j]$ 个城市也会派一名代表坐汽车前往第 $X[j]$ 个城市。

为了避免拥塞，两辆车不应在任何时间点碰面。更具体地，两辆车不能在同一个时间点出现在同一个城市。同样地，两辆车也不应该沿相反的方向同时行驶过同一条道路。 另外，汽车行驶过一条道路时必须完整经过道路并到达道路另一端的城市（换句话说， 汽车不允许在道路中间掉转方向）。但是，汽车可以多次到达一个城市或是多次经过一 条道路。此外，汽车可以在任何时间在任何城市等候。

由于高燃料容量汽车的价格昂贵，两个城市都分别希望选择一条路线，使得两辆汽车所需的最大单位汽油容量最小。每个城市中都有加油站并且供油量是无限的，因此汽车所需的单位汽油容量实际上就是行驶过的道路中最大的单位汽油消耗量。

实现细节

你必须引用 swap.h 头文件。

你必须实现 init 和 getMinimumFuelCapacity 函数。

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)

• $N$：一个整数表示城市数。
• $M$：一个整数表示道路数。
• $U$：一个长为 $M$ 的整数序列表示道路的第一个端点城市。
• $V$：一个长为 $M$ 的整数序列表示道路的第二个端点城市。
• $W$：一个长为 $M$ 的整数序列表示道路的汽油消耗。

该函数将在所有 getMinimumFuelCapacity 的调用前被评测库恰好调用一次。

int getMinimumFuelCapacity(int X, int Y)

• $X$：一个整数表示第一个城市。
• $Y$：一个整数表示第二个城市。
• 该函数必须返回一个整数，表示根据题目描述中的规则，两辆分别从第 $X$ 个城市与第 $Y$ 个城市出发要到达彼此城市的车，它们的单位汽油容量最大值的最小值。若无法满足题目规则则返回 $−1$。

该函数将被评测库调用恰好 $Q$ 次。

样例评测库

样例评测库将读入以下格式的数据：

N M
U[0] V[0] W[0]
U[1] V[1] W[1]
.
.
.
U[M-1] V[M-1] W[M-1]
Q
X[0] Y[0]
X[1] Y[1]
.
.
.
X[Q-1] Y[Q-1]

对每个 getMinimumFuelCapacity 的调用，样例评测库会输出该函数的返回值。

样例一

input

5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

output

3
10
4

explanation

样例二

见下载文件中的 ex_swap2.in 与 ex_swap2.ans。对应的图如下：

数据范围

对于 $100\%$ 的数据，保证：

• $2 \leq N \leq 10^5$
• $N − 1 \leq M \leq 2 \times 10^5$
• $0 \leq U[i] < V [i] < N$
• 任意两个城市间至多存在一条道路直接相连。
• 任意两个城市经过道路可以互相到达。
• $1 \leq W[i] \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq X[j] < Y [j] < N$

实际测试中，前 12 个 subtask 为数据包，后 6 个 subtask 为 6 个子任务。

时间限制：$2 \texttt{s}$

空间限制：$512 \texttt{MB}$

　下载

样例及测评库下载