Doctor and Portals

0

0 votes
Easy
Problem

The Doctor is on an unknown planet and is completly lost. He needs to reach the TARDIS as soon as possible. He knows that there are a few portals though which he can reach the TARDIS. Also, there are N cities numbered from 1 to N connected by N - 1 roads and one can reach from each of these cities to another. Doctor is on city 1. Out of these N cities, there are exactly X cities in which there is a portal to TARDIS. Since, Doctor is in a hurry and you are his companion, he requires you to calculate the minimum number of roads he is required to travel in order to reach a portal.

Input Format:

First line consists of number of cities, N.

Next N - 1 lines consists of two cities, u and v, meaning there is a road connecting cities u and v.

Next line consists of the number X.

Next line consists of X cities which are having a portal.

Output Format:

Ouput a number denoting the minimum number of roads that needs to be covered.

Constraints:

1N105

1u,v105

1XN

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Cities numbered 2 and 4 are having portal out of which 2 is nearest and it takes only 1 road to reach there. So, answer is 1.

Editor Image

?