Youxiang is the most popular anime character in the fantasy world. Today is Youxiang's 2600th birthday, and countless fans have come to the sunflower field in front of Youxiang's house to celebrate her birthday.

Youxiang is very enthusiastic and has organized a series of performances for the fans. Youxiang is also very happy.

At this time, Youxiang discovered something very interesting. There are $n$ plots of land in the sunflower field. In the past, for convenience, Youxiang connected these $n$ plots of land with $n-1$ edges. That is to say, these $n$ plots of land form a tree structure.

There are $n$ fans who have come to the sunflower field. To express their birthday wishes to Youxiang, they chose $c$ colors of clothes, where each color can be represented by an integer from $0$ to $c-1$. Each person stands on a plot of land, and there is only one person on each plot of land. In this way, the sunflower field is decorated with colors. Youxiang saw this and felt very happy.

The fans planned a program: choose two fans $A$ and $B$ (where $A$ and $B$ can be the same), and then the fans on the path from the plot where $A$ is located to the plot where $B$ is located (including the endpoints) will jump in sequence. Youxiang can see the sequence of colors of all the fans (including $A$ and $B$) on the path from $A$ to $B$. Initially, everyone thought that for any two fans (note: $A, B$ and $B, A$ are different, and the sequences they form are opposite, such as red-green-blue and blue-green-red), they would come over, but some people pointed out that this might lead to some identical color sequences, which would cause aesthetic fatigue.

So now they want to ask you, how many different color sequences (substrings) can Youxiang see on this tree in total?

The structure of the sunflower field is special; the number of plots adjacent to any single plot does not exceed 20.

Input

The first line contains two integers $n$ and $c$. They represent the number of plots and the number of colors.

The second line contains $n$ integers from $0$ to $c-1$, separated by spaces, representing the clothing color of the fan on each plot of land in order (here, we give the clothing colors of the fans on each plot of land in the order of the node labels from smallest to largest).

The next $n-1$ lines each contain two integers $u, v$, representing an edge connecting plot $u$ and plot $v$.

Output

Output a single integer representing the answer.

Constraints

For 15% of the data, $n \le 2000$.

For another 15% of the data, every plot is adjacent to at most two other plots.

For another 5% of the data, except for one plot which is adjacent to three other plots, all other plots are adjacent to at most two other plots.

For another 5% of the data, except for two plots which are adjacent to three other plots, all other plots are adjacent to at most two other plots.

For all data, $1 \le n \le 100000$, $1 \le c \le 10$.

Examples

Input 1

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

Output 1

30

Note

Please pay attention to memory limits. On a 64-bit system, the size of a pointer is 8 bytes.