Mimi knitted a scarf for herself. This scarf can be seen as $N$ patches of wool knitted together. Unfortunately, something went very wrong and the scarf ended up as a tree instead of a simple path. The $i^{\text{th}}$ patch is coloured with colour $c_i$, where the colours are numbered. Mimi doesn't want to have to knit another scarf, so she plans on choosing a path in this tree. Particularly, she wants the longest possible scarf.

Additionally, Mimi has poor taste: she abhors stripes and does not want anything resembling a striped pattern in her scarf. As such, the path which she selects cannot contain any subpath $P$ of length larger or equal to a given value $K$ where $c_{P_1}=c_{P_3}=c_{P_5}=\dots$ and $c_{P_2}=c_{P_4}=c_{P_6}=\dots$ where $P_i$ is the $i^{\text{th}}$ node in subpath $P$ from one of $P$'s endpoints. Note that in this problem, the length of a subpath/path is the number of nodes it contains.

Find the length of the longest possible scarf Mimi can get given this constraint.

Constraints

For all subtasks:

$1\le c_i\le N$

Subtask 1 [15%]

$2\le N\le 1000$
$2\le K\le N$

Subtask 2 [15%]

$2\le N\le 200000$
$K=N$

Subtask 3 [70%]

$2\le N\le 200000$
$2\le K\le N$

Input Specification

The first line of input will contain $2$ space-separated integers: $N$ and $K$.
The next line of input will contain $N$ space-separated integers: $c_1,c_2,\dots ,c_N$, indicating that the colour of patch $i$ is $c_i$.
The next $N-1$ lines of input will each contain $2$ integers, $a$ and $b$, indicating that there is an edge between $a$ and $b$ ($1\le a,b\le N$).

Output Specification

A single integer, the length of the longest possible path which satisfies the constraint. In this problem, the length of a path is the number of nodes it contains.

Sample Input 1

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

Sample Output 1

4

Explanation for Sample 1

The best scarf Mimi can get is the one with patches $7,1,2,5$ (there are three other valid paths of the same length other than this path). Note that even though the path from patch $6$ to patch $7$ has a longer length, it is invalid since it contains the subpath from $1$ to $3$.

Sample Input 2

12 4
1 1 1 1 2 2 3 1 3 3 1 2
1 5
5 2
5 3
6 1
6 4
4 10
10 11
11 12
4 7
9 8
7 8

Sample Output 2

6