T438129 「YAC Round 9」咏唱光芒


众所周知，幻想乡有很多 CP。 一共有 $n$ 个人和 $m$ 条关系，第 $i$ 条关系有一个亲密值 $c_i$ 。 假设有一个小姑娘叫 $\text{Reimu}$，另外一个小姑娘叫 $\text{Marisa}$ 。 显然 $\text{Reimu}$ 和 $\text{Marisa}$ 之间存在若干条路径。 每条路径上有若干条关系，我们定义这条 **路径的亲密值** 为：路径上 **所有关系** 的亲密值中的 **最小值**。 同时，我们定义 $\text{Reimu}$ 和 $\text{Marisa}$ 之间的亲密值为：两人之间 **所有可行路径** 的亲密值中的 **最大值**。 若两个人之间不存在可行路径，此时输出 `-1` 。

第一行输入三个整数 $n,m,q$ $\;$ ($2 \le n, q \le 10^5$, $1 \le m \le 3 \times 10^5$) — 分别表示人数、关系条数和询问数。 接下来 $m$ 行，每行包含三个整数 $u_i,v_i,c_i$ $\;$ ($1 \le u_i, v_i \le n$, $u_i \not = v_i$, $1 \le c_i \le 10^6$) — 分别表示 $u_i$ 和 $v_i$ 之间有一条关系，其亲密值为 $c_i$ 。 接下来 $q$ 行，每行包含两个整数 $x_i,y_i$ $\;$ ($1 \le x_i, y_i \le n$, $x_i \not = y_i$) — 表示查询 $x_i$ 和 $y_i$ 之间的亲密值。

输出 $q$ 行，每行输出一个整数表示每个询问的答案。