트리 경로의 서로 다른 가중치 개수

정점이 $N$개인 트리가 있다. 트리는 사이클이 없는 연결 무방향 그래프다. 정점에는 1번부터 $N$번까지, 간선에는 1번부터 $N-1$번까지 번호가 매겨져 있다. 각 정점에는 가중치가 하나씩 붙어 있다.

다음 쿼리를 처리하는 프로그램을 작성하시오.

• u v: $u$번 정점에서 $v$번 정점으로 가는 경로 위에 놓인 정점의 가중치 중 서로 다른 값이 몇 개인지 출력한다. 경로에는 양 끝 정점인 $u$와 $v$도 포함된다.

첫째 줄에 정점의 개수 $N$이 주어진다. ($2 \le N \le 100000$)

둘째 줄에 1번 정점부터 $N$번 정점까지의 가중치가 순서대로 주어진다. 가중치는 $1000000$ 이하의 자연수다.

셋째 줄부터 $N-1$개의 줄에는 $i$번 간선이 잇는 두 정점의 번호 $u$와 $v$가 주어진다. 주어지는 간선은 항상 하나의 트리를 이룬다.

다음 줄에 쿼리의 개수 $M$이 주어진다. ($1 \le M \le 100000$)

이어지는 $M$개의 줄에 쿼리가 한 줄에 하나씩 u v 형식으로 주어진다. $u$와 $v$는 모두 1 이상 $N$ 이하이고, 두 값이 같은 쿼리도 주어진다.

각 쿼리의 결과를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.