405978: GYM102201 F Fruit Tree

In the backyard of Seoul Science High School, there is a magical tree with $$$N$$$ vertices, where every vertex contains a single fruit. (A tree is a connected undirected graph with $$$N-1$$$ edges.)

Although it is prohibited to pick any fruits from the tree, students naturally want to secretly pick some fruit to eat. To prevent being caught by the teacher, they use the following procedure to choose a fruit to pick:

• Choose two vertex $$$s, e$$$ in the tree, and consider all fruits lying in the unique path from $$$s$$$ to $$$e$$$. Fruits in vertex $$$s, e$$$ are also considered.
• Among the fruits in a path, if there is a type of fruit that forms a majority, student pick that fruit and eat. A type of fruit forms a majority if the count of such fruits in a path is strictly larger than half of the total number of fruits in the path.

Of course, they are very nice students, so they never actually pick any of the fruits. They simply think of it. :)

Being exceptionally nice students, they naturally extended their thought experiment as a query problem. Thus, given $$$Q$$$ independent queries, you should find the answer or state that no majority exists. Can you solve it?

The first line contains two integers $$$N, Q$$$. ($$$1 \le N, Q \le 250 000$$$).

In the next line, $$$N$$$ integers $$$c_i$$$ is given, denoting the type of fruit in vertex $$$i$$$. ($$$1 \le c_i \le N$$$).

In the next $$$N-1$$$ lines, two integers $$$a_i, b_i$$$ denoting endpoints of each edge are given. ($$$1 \le a_i, b_i \le N, a_i \neq b_i$$$).

In the next $$$Q$$$ lines, two integers $$$s_i, e_i$$$ denoting two endpoints of each path are given. ($$$1 \le s_i, e_i \le N$$$).

Print $$$Q$$$ lines. For each line, print a single integer denoting the type of fruit that forms a majority in a given path. If there exists no majority in the given path, print $$$-1$$$.

7 4
3 1 1 2 1 1 2
1 3
7 5
2 3
5 3
5 6
4 5
1 4
7 2
3 3
4 7

-1
1
1
2