Description

成都有 $n$ 家火锅店，编号从 $1$ 到 $n$，第 $i$ 家火锅店的火锅辣度为 $w_i$。辣度越高越辣，辣度较低则更温和（当然还是要小心辣）。

我们可以把这 $n$ 家火锅店看作无向图中的 $n$ 个节点，图上有 $m$ 条边。现在有 $q$ 位游客想要尝试火锅。给定游客当前所在的火锅店以及他们能承受的最大辣度，请你计算每位游客距离他能够接受的最近火锅店的最短距离。

在本题中，路径的距离定义为路径上边的数量。

Input Format

每个测试文件只有一组测试数据。

第一行包含三个整数 $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$。

Output Format

输出 $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

Hint

由 ChatGPT 5 翻译