과일 나무

서울과학고등학교 뒷마당에는 $N$개의 정점으로 이루어진 마법의 나무가 있고, 각 정점에는 과일이 하나씩 달려 있다. (나무는 $N-1$개의 간선으로 이루어진 연결 무향 그래프이다.)

나무에서 과일을 따는 것은 금지되어 있지만, 학생들은 몰래 과일을 따 먹고 싶어 한다. 선생님에게 들키지 않으려고 학생들은 다음과 같은 방법으로 딸 과일을 고른다.

• 나무에서 두 정점 $s, e$를 고르고, $s$에서 $e$로 가는 유일한 경로에 있는 모든 과일을 생각한다. 정점 $s, e$에 있는 과일도 포함한다.
• 경로에 있는 과일 중에서 개수가 과반수를 차지하는 종류가 있으면, 학생은 그 과일을 골라 먹는다. 어떤 종류의 과일이 과반수를 차지한다는 것은, 경로에서 그 과일의 개수가 전체 과일 개수의 절반보다 엄격하게 큰 경우를 말한다.

물론 학생들은 착한 학생이라 실제로 과일을 따지는 않는다. 그냥 생각만 한다. :)

착한 학생답게, 학생들은 이 생각 실험을 쿼리 문제로 확장했다. $Q$개의 독립적인 쿼리가 주어질 때, 각 쿼리에 대해 답을 구하거나 과반수를 차지하는 과일이 없다고 판단해야 한다. 이 문제를 풀 수 있겠는가?

첫째 줄에 두 정수 $N, Q$가 주어진다. ($1 \le N, Q \le 250 000$)

다음 줄에 $N$개의 정수 $c\_i$가 주어지며, 정점 $i$에 있는 과일의 종류를 나타낸다. ($1 \le c\_i \le N$)

다음 $N-1$개의 줄에 각 간선의 두 끝점 $a\_i, b\_i$가 주어진다. ($1 \le a\_i, b\_i \le N, a\_i \neq b\_i$)

다음 $Q$개의 줄에 각 경로의 두 끝점 $s\_i, e\_i$가 주어진다. ($1 \le s\_i, e\_i \le N$)

$Q$개의 줄을 출력한다. 각 줄에는 주어진 경로에서 과반수를 차지하는 과일의 종류를 하나의 정수로 출력한다. 주어진 경로에 과반수를 차지하는 과일이 없으면 $-1$을 출력한다.