경주

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

선거가 다가오자 바이트타운(Bytetown) 시장은 지지율을 높이려고 육상 대회를 열기로 했다. 하지만 바이트타운에는 경기장이 없어서 모든 종목을 거리에서 진행해야 한다. 시장은 종목을 달리기 경주로만 한정하고, 경로(route) 배치를 도와달라고 부탁했다.

바이트타운에는 nn개의 교차로와 n1n-1개의 거리(도로)가 있다. 이 거리들을 이용하면 임의의 두 교차로 사이를 오갈 수 있다. 즉, 교차로와 거리는 하나의 트리를 이룬다. 각 경로는 한 교차로에서 출발해 여러 개의 거리를 지나 다른 교차로에서 끝난다. 시장은 되도록 많은 종목을 동시에 열고 싶어 하므로, 경로의 개수를 최대로 만들어야 한다.

안전을 위해 서로 다른 두 경로는 어떤 교차로도, 어떤 거리도 공유할 수 없다. 또한 모든 교차로가 경주의 출발점이나 도착점이 될 수 있는 것은 아니다. 출발점과 도착점은 지정된 교차로들 중에서만 고를 수 있으며, 경로가 중간에 지나가기만 하는 교차로에는 이런 제약이 없다.

동시에 열 수 있는 경주(경로)의 최대 개수를 구하여라.

입력

첫째 줄에 교차로의 수 nn (1n1,000,0001 \le n \le 1{,}000{,}000)이 주어진다. 교차로는 11번부터 nn번까지 번호가 매겨져 있다.

다음 n1n-1개의 줄에는 각 거리의 정보가 주어진다. 각 줄에는 그 거리의 양 끝 교차로 번호를 나타내는 두 정수 aabb (1a,bn1 \le a, b \le n, aba \ne b)가 공백으로 구분되어 주어진다.

그다음 줄(n+1n+1번째 줄)에는 경주의 출발점 또는 도착점이 될 수 있는 교차로의 수 mm (0mn0 \le m \le n)이 주어진다.

마지막 줄에는 그러한 교차로 mm개의 번호가 공백으로 구분되어 주어진다. 각 번호는 서로 다르며 모두 [1,n][1, n] 범위 안에 있다.

출력

바이트타운에서 동시에 열 수 있는 경주의 최대 개수를 정수 하나로 출력한다.