There are hotpot restaurants numbered from to in Chengdu and the -th restaurant serves hotpots of a certain spicy value . 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 restaurants as nodes on an undirected graph with edges. Now we have 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 ,  and  () indicating the number of restaurants, the number of edges and the number of tourists.
The second line contains  integers  () where  indicates the spicy value of the -th restaurant.
For the following  lines, the -th line contains two integers  and  (, ) indicating an edge connecting restaurant  and .
For the following  lines, the -th line contains two integers  and  (, ) indicating that the i-th tourist is currently at restaurant  and that the maximum spicy value he can accept is .

输出描述:

Output  lines where the -th line contains one integer indicating the shortest distance between the -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