P7276 Gifts for Friends

M and B are a pair of good friends, and they both like strawberries.

Given a tree $T$ with $n$ nodes, the nodes are numbered from $1$ to $n$. At time $0$, both M and B are at node $1$. At the beginning of each time step starting from time $1$, M and B can each choose to either move to a node directly connected to their current node, or stay at their current node. There are $k$ strawberries on the tree, located on $k$ different nodes. M and B want to collect all the strawberries. At the end of any time step, if M or B is at a node that has a strawberry, then that strawberry is collected. They do not want to spend too much time, so you need to answer: at the end of which earliest time step can M and B collect all strawberries and both return to node $1$.

The first line contains two integers $n, k$ ($1 \leq k \leq n \leq 415$), representing the number of nodes in the tree and the number of strawberries. The next $n - 1$ lines each contain two integers $u$ and $v$, indicating that there is an edge between $u$ and $v$ in the tree. The next line contains $k$ distinct integers $a_1, a_2, \ldots , a_k$, representing the nodes where the $k$ strawberries are located.

Output one integer in one line, the required answer.

**[Sample Explanation #1]**  M's route is: $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$. B's route is: $1 \to 5 \to 6 \to 7 \to 6 \to 5 \to 1$. --- **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 ($6$ points): $n \leq 3$. - Subtask 2 ($1$ point): $k = 1$. - Subtask 3 ($11$ points): $n \leq 7$. - Subtask 4 ($17$ points): $k \leq 20$. - Subtask 5 ($42$ points): $n \leq 90$. - Subtask 6 ($23$ points): no special constraints. For $100\%$ of the testdata, $1 \leq k \leq n \leq 415$, $1 \leq u, v \leq n$. Translated by ChatGPT 5