동물원

요조는 올해 초 새로 지은 동물원에 입사했다. 오늘 그는 특별한 임무를 받았다. 방문객이 점점 줄어드는 원인을 찾아내는 일이다. 요조는 우리들과 그 사이를 잇는 길을 살피다가, 문제가 관람 코스가 지나치게 단조롭다는 데 있다고 의심했다.

동물원에는 1번부터 $N$번까지 번호가 붙은 $N$개의 우리와, 두 우리를 잇는 $N-1$개의 오솔길이 있다. 어떤 두 우리 사이에도 길이 있다(반드시 직접 연결된 길일 필요는 없다). 각 우리에는 한 종류의 동물이 산다. $i$번 우리에는 종류가 $v_i$인 동물이 있다.

요조는 길의 단조로움을 구해 달라고 부탁했다. 길의 단조로움은 길 위에 있는 우리(길의 양 끝 우리 포함)에서 가장 많이 나타나는 동물의 등장 횟수이다. 예를 들어 길 위의 우리에 동물 2, 3, 1, 2, 2, 3이 있다면, 동물 2가 3번 나타나므로 단조로움은 3이다.

$Q$개의 우리 쌍 $(a, b)$에 대해, 우리 $a$에서 우리 $b$까지 가는 (가장 짧은) 길의 단조로움을 구하라.

첫 줄에 자연수 $N$과 $Q$가 주어진다 ($1 \le N \le 10^5$, $1 \le Q \le 10^5$).

둘째 줄에 $N$개의 자연수 $v_i$가 주어진다 ($1 \le v_i \le 10^9$). $v_i$는 $i$번 우리에 있는 동물의 종류이다.

다음 $N-1$개 줄에는 두 자연수 $x_i$, $y_i$가 주어진다 ($1 \le x_i, y_i \le N$). $i$번째 오솔길이 잇는 두 우리를 뜻한다.

다음 $Q$개 줄에는 두 자연수 $a_i$, $b_i$가 주어진다 ($1 \le a_i, b_i \le N$). 우리 $a_i$에서 우리 $b_i$까지 가는 길의 단조로움을 구해야 한다.

$Q$개 줄에 문제에서 요구한 답을 차례대로 출력한다.

첫 번째 예제에 대한 설명이다. 각 노드에는 우리 번호와 동물 종류가 적혀 있다.

1번 질의에서 길 위의 우리는 차례대로 1번과 2번이다. 종류 1과 2가 각각 한 번씩 나타나므로 단조로움은 $1$이다.

2번 질의에서 길 위의 우리는 1, 2, 4번이다. 종류 1이 두 번 나타나므로 단조로움은 $2$이다.

3번 질의에서 길 위의 우리는 4, 2, 1, 3, 7번이다. 종류 1이 우리 1, 4, 7에서 세 번 나타난다.

4번 질의에서 길 위의 우리는 2, 1, 3번이다. 종류 2가 두 번, 종류 1이 한 번 나타난다.

5번 질의에서 길 위의 우리는 5, 2, 1, 3, 6번이다. 종류 2가 네 번, 종류 1이 한 번 나타난다.