E-小柒的神器_牛客练习赛135

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小柒收集了 $n$ 把神器，第 $i$ 把神器的能量为 $a_i$ 。这些神器之间有 $m$ 对直接融合关系，第 $i$ 对关系记为 $(u_i,v_i)$ ，代表第 $u_i$ 把神器和第 $v_i$ 把神器可以融合。
$\hspace{15pt}$ 小柒现在获得了一枚储物戒，最初储物戒是空的，你可以将任意一把神器放入储物戒而不用付出任何代价；其余每把神器只有在储物戒中存在与之具有直接融合关系的神器时才能放入，放入代价为两者能量之和。形式化地，记 $\Bbb S$ 为已经放入储物戒的神器集合，若存在 $i\in \Bbb S$ 且第 $i,j$ 把神器具有直接融合关系，才可以将第 $j$ 把神器放入，代价为 $a_i+a_j$ 。

$\hspace{15pt}$ 现在，小柒会进行 $q$ 次独立询问，每次询问指定一个区间 $[l,r]$ ，你需要求解：能否将区间 $[l,r]$ 中的神器都放入储物戒？如果可以，输出放入过程中，单次放入所需代价的最大值至少是多少；否则，输出 $-1$ 。

输入描述:

第一行输入两个整数  代表神器的数量、具有直接融合关系的神器对数、询问次数。 
第二行输入  个整数  代表每一把神器的能量。 
此后  行，每行输入两个整数  代表第  把神器和第  把神器具有直接融合关系。 
此后  行，每行输入两个整数  代表一次询问。

输出描述:

对于每次询问，新起一行。如果不能将区间中的神器都放入储物戒，直接输出 ；否则输出单次放入所需代价的最大值的最小值。

示例1

输入

复制

6 5 4
8 2 6 4 5 9
2 3
1 3
4 5
3 4
4 6
1 4
3 4
5 6
6 6

输出

复制

说明

对于第一次询问中，选择了第  把神器，其中，第  把神器可以与第  把神器融合，因此放入顺序为：
直接放入第  把神器，代价为 ；
放入第  把神器，代价为 ；
放入第  把神器，代价为 ；
放入第  把神器，代价为 ；
因此，最大代价为 。我们可以证明，不存在一种更优的放入顺序使得单次放入的最大代价小于 。

对于第二次询问，第  把神器与第  把神器融合的代价最大，为 。同样可以证明这是最小值。

对于第四次询问，区间中只有一把神器，因此不需要进行融合操作。

示例2

输入

复制

输出

复制

18
-1

说明

对于第一次询问，最优策略为：
直接放入第  把神器，代价为 ；
放入第  把神器，代价为 ；
放入第  把神器，代价为 ；
至此，第  把神器都在储物戒中，过程最大代价为 。