D. 食肉斯特想要旅游

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

食肉斯特是一个闪电侠。

设奇妙城市里一共有 个点,这 个点由 条双向边连接而成,每条边有一个权值 表示这条道路限速

食肉斯特决定旅游 天,每天以相同的速度从 走到

现在他想知道他每天旅游能用最快的速度是多少。

形式化的说,给定 个询问,问从 所有路径中 路径中最小边权 的最大值,若不能到达就输出-1。

输入格式

第一行输入三个正整数

接下来 行输入两个正整数 表示从 有一条边,限重为

接下来有一个正整数

接下来 行 输入两个正整数 ,

输出格式

一共 行,每行输出其最大速度,若不能到达,则输出 -1。

样例

样例输入

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

样例输出

3
-1
3

数据范围与提示

, , , .