## Back To School '18: Trucking Troubles II

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Java 1.8s
Memory limit: 256M

Author:
Problem types

Yi is one of many hardworking truck drivers in a mysterious land. In this mysterious land, there are villages connected by two-way roads. His job, like many others, is to transport mysterious substances from one village to another through these roads. Each village can travel to any other village using these roads. At each village, there is a population of residents.

Yi has trips. For each trip, he must travel from village to village . He wants to find the first village on the path from to where the population is greater than or equal to (including village ). If there are no villages with a population greater than or equal to , or if it is impossible to travel between village and village (more to follow in the next paragraph), print -1.

Truck drivers, as it turns out, are not always very careful (unlike Yi). Sometimes, after Yi is finished his trip, and before his , the mysterious substance that the other truck driver is carrying will spill onto road , permanently destroying road for any of Yi's subsequent trips (In particular, trip to trip ). This will happen times. Note that this may render future trips to be impossible for Yi, in which case -1 should be outputted for those trips.

#### Input Specification

The first line will contain three integers, .

The second line will contain integers, , the population of each village.

The next lines will each contain two integers, , meaning that there is a road connecting village and village .

The next lines will each contain two integers, . This means that the road (from the order in the input) is destroyed immediately after Yi's trip. It is guaranteed that is unique, however it is not guaranteed that is unique.

The next lines will each contain a trip of the form a b k .

#### Output Specification

For each trip, output the first village on the path from to where the population is greater than or equal to (including village ). If there is no path from to , or if no village has a population greater than or equal to on the path, print -1.

No further constraints.

#### Sample Input 1

8 8 0
2 8 4 1 10 0 2 3
1 2
2 3
2 4
2 5
5 6
1 7
7 8
8 6 8
1 3 1
4 3 9
6 6 0
1 8 2
8 1 2
3 3 5
7 4 3

#### Sample Output 1

2
1
-1
6
1
8
-1
2

#### Sample Input 2

9 5 2
100 0 3 0 7 5 1 0 2
1 2
2 3
1 4
4 5
4 6
6 7
6 8
6 9
4 1
3 3
2 9 2
3 6 1
7 1 99
4 2 6
3 6 1

#### Sample Output 2

1
3
1
-1
-1