Minimize Maximum Distance Among Selected Black Nodes

You are given a tree with n nodes numbered from 1 to n. Each node is colored either black or white. Your task is to choose exactly m black nodes such that the maximum distance between any two of the chosen nodes is minimized. Output this minimized maximum distance.

Notes:

• The tree is an undirected connected acyclic graph.
• The distance between two nodes is defined as the number of edges on the unique simple path connecting them.

It is guaranteed that there are at least m black nodes in the tree.

inputFormat

The input is given as follows:

 n m
 c1 c2 ... cn
 u1 v1
 u2 v2
 ...
 un-1 vn-1

Here, the first line contains two integers n and m where n is the number of nodes and m is the number of black nodes to choose. The second line contains n characters (each either B or W) separated by spaces, representing the colors of the nodes. Each of the next n-1 lines describes an edge of the tree by two integers u and v (1-indexed) indicating there is an edge between nodes u and v.

outputFormat

Output a single integer — the minimized maximum distance between any two chosen black nodes.

sample

5 2
B W B W B
1 2
2 3
3 4
4 5

2