408429: GYM103117 L Spicy Restaurant

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