题目描述

给你一个 $n$ 个点 $m$ 条边的无向图，每条边都有个边权。你要回答 $q$ 次询问，每次给定 两个点 $u,v$ ，回答所有从 $u$ 到 $v$ 的简单路径（即没有重复点的路径）中，第二大的边权的最小值是多少。

如果一条路径，只有一条边，那么我们认为边权第二大的边权为 $0$ 。

输入格式

第一行，三个整数 $n,m,q$ ，分别表示点数，边数和询问个数。

接下来 $m$ 行，每行三个整数 $x,y,w$ ，表示有一条从 $x$ 到 $y$ 的边权为 $w$ 的无向边，保证没有自环，即 $x≠y$ ，可能有重边。

接下来 $q$ 行，每行两个整数 $u,v$ ，表示一个询问，保证 $u≠v$ 。

输出格式

一共 $q$ 行，对于每个询问，输出一个整数表示答案。如果 $u,v$ 不连通，那么输出 $−1$ 。

样例 1 输入

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

样例 1 输出

0
2
-1

样例 2 输入

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

样例 2 输出

2
0
3
2
5

样例 3 输入输出

见下发文件。

数据规模

共十组数据。

测试点 $1,2,3$ 满足 $1 ≤ n,q ≤ 100,1 ≤ m ≤ 200$ 。

测试点 $4,5$ 满足 $1 ≤ n,q ≤ 10^3,1 ≤ m ≤ 2 × 10^3$ 。

测试点 $6,7$ 满足整个图是一棵树。

对于 $100\%$ 的数据，满足 $1 ≤ n,q ≤ 10^5 , 1 ≤ m ≤ 2 × 10^5, 1 ≤ w ≤ 10^9$ 。