题目描述

There are $n$ hotpot restaurants numbered from $1$ to $n$ in Chengdu and the $i$-th restaurant serves hotpots of a certain spicy value $w_i$. A higher spicy value indicates a hotter taste, while a lower spicy value is more gentle (still need to be very careful, though).

We can consider these $n$ restaurants as nodes on an undirected graph with $m$ edges. Now we have $q$ tourists who want to give the hotpots a try. Given the current positions of the tourists and the maximum spicy value they can bear, your task is to calculate the shortest distance between a tourist and the closest restaurant he can accept.

In this problem we define the distance of a path as the number of edges in the path.

输入格式

There is only one test case in each test file.

The first line contains three integers $n$, $m$ and $q$ ($1 \le n, m \le 10^5,1 \le q \le 5 \times 10^5$) indicating the number of restaurants, the number of edges and the number of tourists.

The second line contains $n$ integers $w_1, w_2, \cdots, w_n$ ($1 \le w_i \le 100$) where $w_i$ indicates the spicy value of the $i$-th restaurant.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) indicating an edge connecting restaurant $u_i$ and $v_i$.

For the following $q$ lines, the $i$-th line contains two integers $p_i$ and $a_i$ ($1 \le p_i \le n$, $1 \le a_i \le 100$) indicating that the $i$-th tourist is currently at restaurant $p_i$ and that the maximum spicy value he can accept is $a_i$.

输出格式

Output $q$ lines where the $i$-th line contains one integer indicating the shortest distance between the $i$-th tourist and the closest restaurant he can accept. If there is no such restaurant, output -1 instead.

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