The Park
Limits: 2 sec., 256 MiB
Zenyk and Marichka have walked in the park for a very long time and at one point Zenyk noticed that Marichka had disappeared. He wants to find her as soon as possible and asks you for help. Zenyk knows that the park consists of \(N\) clearings and \(N-1\) trails that lead from one clearing to another. The trails are trodden in such a way that from any clearing you can reach any other clearing by walking only on the trails. Now Zenyk is on the clearing number 0, and Marichka is waiting for him on a random clearing. Zenyk also knows that there are \(M\) Marichka’s ex-boyfriends and they walk on clearings with numbers \(e_i\) and she is not there. With this information, tell Zenyk, what is the minimum time Zenyk will be guaranteed to find Marichka, provided that the walking on one trail takes 1 minute.
The park has at least 1 clearing on which there isn’t any of Marichka’s ex-boyfriend.
Input
In the first line, there are two integers \(N\) and \(M\) — the number of clearings and the number of clearings where Marichka’s ex-boyfriends walk.
In the next line, there are \(M\) numbers \(e_i\) — indices of clearings on which Marichka’s ex-boyfriends walk. All indices are unique.
In the following \(N-1\) lines there are two numbers separated by space \(u_i\) and \(v_i\) — indices of clearings which are connected by trail.
Clearings are numbered from 0.
Output
Print one number — the minimum time in minutes in which Zenyk is guaranteed to find Marichka.
Constraints
\(2 \le N \le 5 \cdot 10^{5}\),
\(0 \le M \le N-2\),
\(0 \le e_{i} \le N-1\),
\(0 \le u_i, v_i \le N-1\),
\(u_i \ne v_i\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 0 0 1 0 2 | 3 |
Input (stdin) | Output (stdout) |
---|---|
7 3 0 3 6 0 1 1 6 0 2 2 3 2 4 3 5 | 7 |
Notes
In the first example, Zenyk can be guaranteed to find Marichka if he goes around all the clearings. One of the shortest ways to do this is \(0 \to 1 \to 0 \to 2\).
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|