题目描述

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

输入格式

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

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

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

输出格式

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

样例

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

数据范围与提示

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