Lazy Shepherds on a Tree

Given a tree with \(N\) nodes numbered from 1 to \(N\), and \(K\) sheep located at \(K\) distinct nodes, your task is to assign some shepherds to nodes in the tree in order to guard all the sheep.

The lazy shepherds follow a peculiar rule: each shepherd only guards the sheep(s) which are the closest to him. In other words, a shepherd placed at a node \(x\) will guard a sheep at node \(s\) if \(d(x,s) = \min\{d(x, t) : t \text{ is a sheep}\}\). If there are multiple sheep achieving that minimum distance, he will guard them all. Note that a shepherd may be placed at the same node as a sheep; however, in that case his distance to that sheep is 0 and he will only guard that one sheep.

Your goal is to choose a set of nodes to place shepherds (each node can have at most one shepherd) such that every sheep is guarded by at least one shepherd and the total number of shepherds is minimized.

Hint: A shepherd placed at a non-sheep node may guard multiple sheep if the distances are equal (for example, if it lies exactly at the middle of the path between two sheep and that distance is the minimum from that node).

The tree is given by \(N-1\) edges. Use the optimal strategy to cover all sheep.

Mathematical formulation:

For any node \(x\) in the tree, define \[ d(x)=\min_{s\in S} d(x,s), \] where \(S\) is the set of sheep nodes and \(d(x,s)\) is the distance between nodes \(x\) and \(s\). A shepherd placed at node \(x\) guards all sheep \(s\) satisfying \[ d(x,s)=d(x). \] Determine the minimum number of shepherds needed so that every sheep appears as a guard target in at least one shepherd's assignment.

inputFormat

The first line contains two integers \(N\) and \(K\) \((1 \leq K \leq N)\) — the number of nodes in the tree and the number of sheep.

Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) \((1 \leq u,v \leq N)\) indicating there is an edge between nodes \(u\) and \(v\).

The last line contains \(K\) distinct integers representing the nodes that contain sheep.

outputFormat

Output a single integer: the minimum number of shepherds needed such that every sheep is guarded.

sample

2 2
1 2
1 2

2