Easyhost's servers are distributed throughout the city. Unfortunately, some of them are not secure. You are given the map of the city, represented as a tree with N nodes. A team of K network specialists is given the task to secure K distinct servers. Each specialist is placed in one of the tree's nodes, and must secure exactly one server. Each server is represented by one node, and becomes secure when a specialist arrives in the respective node. All specialists have a moving speed equal to one edge per second.
Your task is to find the minimum number of seconds necessary to secure all servers.
InputThe first line of input contains integers N and K.
The second line of input contains sequence a1, a2, …, ak, where ai is the initial node of the ith specialist.
The third line of input contains sequence b1, b2, …, bk, where bi is the node corresponding to the ith server.
The last N-1 lines of input contain the tree's edges. Each of these lines holds a pair x y, denoting an edge between nodes x and y.
The only line of output should contain a single integer — the minimum number of seconds after which all servers are secured, considering that each specialist operates optimally.
- 1 ≤ N ≤ 104
- 1 ≤ K ≤ min(300, N)
- 1 ≤ ai, bi ≤ N
- Multiple specialists may be placed on the same node.
6 11 9
7 3 10
It's easy to notice that we have a complete bipartite graph with K nodes. One set contains the nodes of the K specialists. The other contains the nodes of the K servers.
It is complete because we have a path between any pair of nodes.
Now, the answer for the problem is the minimum cost such that if we consider only the edges with cost less or equal to that cost, we have a perfect match. If we increase that cost, the match can only increase or stay the same.
Therefore, we can binary search for the answer.