You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

有从 $1$ 到 $n$ 编号的 $n$ 家鬼屋，每家鬼屋都有一定的惊吓程度 $w_i$。惊吓程度值越高，体验越惊悚；值越低，氛围越温和（但仍需谨慎体验）。

我们可以将这些 $n$ 家鬼屋视为一个无向图上的节点，该图有 $m$ 条边。现在，有 $q$ 名访客想去这些鬼屋体验。给定访客的当前位置和他们能承受的最大惊吓程度值，你的任务是计算访客与他能接受的最近鬼屋之间的最短距离。 在这个问题中，路径的距离定义为路径中的边数。

输入

每个测试文件中只有一个测试用例。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 10^5$，$1 \le q \le 5 \times 10^5$），分别表示鬼屋数量、边数量和访客数量。

第二行包含 $n$ 个整数 $w_1, w_2, \cdots, w_n$（$1 \le w_i \le 100$），其中 $w_i$ 表示第 $i$ 个鬼屋的惊吓程度。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示连接鬼屋 $u_i$ 和 $v_i$ 的边。

再接下来的 $q$ 行，每行包含两个整数 $p_i$ 和 $a_i$（$1 \le p_i \le n$，$1 \le a_i \le 100$），表示第 $i$ 个访客目前在鬼屋 $p_i$，他能接受的最大惊吓程度是 $a_i$。

输出

输出 $q$ 行，其中第 $i$ 行包含一个整数，表示第 $i$ 个访客与他能接受的最近鬼屋之间的最短距离。如果没有这样的鬼屋，则输出 "-1"。

样例输入输出

输入样例

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

输出样例

-1
2
1
1
0 

限制与约定

对于 $40\%$ 的样例，（$1 \le n \le 100 , 1 \le m \le 1000$，$1 \le q \le 100$）

对于 $100\%$ 的样例，点数 $n$ , 边数 $m$ ，游客数 $q$（$1 \le n, m \le 10^5$，$1 \le q \le 5 \times 10^5$）每个鬼屋的惊吓程度 $w$（$1 \le w_i \le 100$）,对于每次查询的 $p,a$（$1 \le p_i \le n$，$1 \le a_i \le 100$）,给定的结点 $u,v$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），保证图连通

• 时间限制: $3 s$
• 空间限制: $256 MB$