## Monkey Motel

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Java 3.0s
Python 3.0s
Memory limit: 256M
Java 512M
Python 512M

Authors:
Problem type

William, the monkey, is an investor currently checking out the AAC Motel, an oak tree home to treehouses each labeled with an ID from to , connected by bi-directional branches. Furthermore, each treehouse has a room size of and William sets the treehouse with ID to be the root of the whole motel.

We define the price of a treehouse to be the smallest positive integer that is not present as a room size among all treehouses in the subtree rooted at .

Over the next days of his visit, he will provide the owner with a value , and among all treehouses with price greater than or equal to , the owner must reply with the ID of the treehouse with the minimum sized subtree. If there are multiple treehouses satisfying the conditions, William asks for the treehouse with the minimum ID. On the other hand, if there are no treehouses that satisfy a query, the owner must reply with -1.

Help the owner answer William's queries to avoid eviction!

#### Constraints   ##### Subtask 1 [10%] #### Input Specification

The first line of input contains two space-separated integers, and representing the number of treehouses and queries, respectively.

The second line of input contains space-separated integers .

The next lines each contain integers and representing a branch between two treehouses.

The final lines will each contain a single integer .

#### Output Specification

Output lines, each with the answer for the query. If there are no treehouses satisfying the conditions, output -1.

#### Sample Input

6 2
5 1 3 2 4 6
1 2
2 3
2 6
1 4
4 5
4
13

#### Sample Output

1
-1

#### Sample Explanation

Consider the depicted tree below, with the black text inside each treehouse being the ID, the red text above being the room size, and the blue text below being the price. For the first query, the only treehouse with price is .

For the second query, there are no treehouses with price so -1 is the answer.