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 1\,000~
~2 \le K \le N~

Subtask 2 [15%]

~2 \le N \le 200\,000~
~K=N~

Subtask 3 [70%]

~2 \le N \le 200\,000~
~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