You are given a tree with N nodes. \nThe tree nodes are numbered from 1 to N. \nEach node has an integer weight.

\n\n

We will ask you to perform the following operation:

\n

u v : ask for how many different integers that represent the weight of nodes there are on the path from u to v.

\n\n

Input

\n\n

In the first line there are two integers N and M. (N <= 40000, M <= 100000)

\n

In the second line there are N integers. The i-th integer denotes the weight of the i-th node.

\n

In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).

\n

In the next M lines, each line contains two integers u v, which means an operation asking for how many different integers that represent the weight of nodes there are on the path from u to v.

\n\n

Output

\n

For each operation, print its result.

\n\n

Example

\n

Input:\n8 2\n105 2 9 3 8 5 7 7\n1 2\n1 3\n1 4\n3 5\n3 6\n3 7\n4 8\n2 5\n7 8

\n\n

Output:\n4\n4

统计

递交统计

Count on a tree II

信息

状态

开发

支持

还没有账户？

登录