#4642. 模板.最小瓶颈路

模板.最小瓶颈路

Description

给定一个包含 n n 个节点和 m m 条边的图,每条边有一个权值。 你的任务是回答 k k 个询问,每个询问包含两个正整数 s s t t 表示起点和终点,要求寻找从 s s t t 的一条路径,使得路径上权值最大的一条边权值最小。

Input

第一行包含三个整数 n n m m k k ,分别表示 n n 个节点, m m 条路径, k k 个询问。

接下来 m m 行,每行三个整数 u u , v v , w w , 表示一个由 u u v v 的长度为 w w 的双向边。

再接下来 k k 行,每行两个整数 s s , t t ,表示询问从 s s 连接到 t t 的所有路径中单边长度最大值的最小值。

Output

输出包含 k k 行,每一行包含一个整数 p p p p 表示 s s 连接到 t t 的所有路径中单边长度最大值的最小值。另外,如果 s s t t 没有路径相连通,输出 -1 即可。

Samples

8 11 3
1 2 10
2 5 50
3 4 60
7 5 60
3 6 30
1 5 30
6 7 20
1 7 70
2 3 20
3 5 40
2 6 90
1 7
2 8
6 2
30
-1
30

Limitation

对于 30% 30\% 的数据 n100,m1000,k100,w1000 n \leq 100, m \leq 1000, k \leq 100, w \leq 1000
对于 70% 70\% 的数据 $ n \leq 1000, m \leq 10000, k \leq 1000, w \leq 100000 $
对于 100% 100\% 的数据 $ n \leq 1000, m \leq 100000, k \leq 1000, w \leq 10000000 $
本题可能会有重边。
为了避免 Special Judge,本题所有的 w w 均不相同。