Problem B: Giants

Problem B: Giants

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2310  Solved: 431
[Submit][Status][Web Board]


There are \(n\) cities numbered from \(1\) to \(n\), and \(n-1\) roads connecting these \(n\) cities, i.e., it is a tree with \(n\) nodes. Each road takes one day for giants to travel through. City \(1\) is a huge city and can host all giants. However, other cities are small. Each small city can only host one giant at the same time. Initially, some giants are in small cities. They set out at the same time and want to gather in city \(1\). In each day, every giant can choose to go to another city or stay at the current city. Please find the minimum needed days for all giants to gather in city \(1\).


The first line contains an integer \(n(2\leq n\leq 400,000)\) which means the number of cities.

Then \(n-1\) lines follow. Each line contains two integers \(u,v(1\leq u, v\leq n)\) which means a road between city \(u\) and city \(v\).

Then one line contains an integer \(m(1\leq m\leq n-1)\) which means the number of giants.

Then one line contains \(m\) integers which describe the indices of the cities where these giants are in initially. Different giant is in a different small city initially.


Print the minimum number of days needed for all giants to gather in city \(1\).

Sample Input

1 2
1 3
3 4
3 5
2 3 4 5

Sample Output



Explanation for the example: In day 1, two giants in city 2 and 3 can go to city 1. However, two giants in city 4 and 5 cannot both go to city 3 since city 3 is small. One of the two has to stay at the current city in day 1, and arrives in city 1 at the end of day 3. Therefore, the answer is 3.