路径查询

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

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

输入格式 第一行，三个整数�, �, �，分别表示点数，边数和询问个数。

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

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

输出格式 一共�行，对于每个询问，输出一个整数表示答案。如果�, �不连通，那么输出−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 ≤ �, � ≤ 100,1 ≤ � ≤ 200。

测试点 4,5 满足 1 ≤ �, � ≤ 103 , 1 ≤ � ≤ 2 × 103 。

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

对于 100%的数据，满足 1 ≤ �, � ≤ 105 , 1 ≤ � ≤ 2 × 105 , 1 ≤ � ≤ 109 。