27568번 - Branch Manager 다국어

문제

You are managing a transportation network of one-way roads between cities. People travel through the transportation network one by one in order all starting from the same city, and each person waits for the person before them to stop moving before starting. The people follow a simple algorithm until they reach their destination: they will look at all the outgoing roads from the current city, and choose the one that leads to the city with the smallest label. A person will stop when they either reach their destination, or reach a city with no outgoing roads. If at any point someone fails to reach their destination, the rest of the people still waiting in line will leave.

Before each person enters the transportation network, you can permanently close down any subset of roads to guarantee they reach their destination. The roads that you choose to close down will not be available for future people.

There are $n$ cities, labeled from 1ドル$ to $n$. There are $n-1$ directed roads, and each road will always be from a lower labeled city to a higher labeled one. The network will form a rooted tree with city 1ドル$ as the root. There are $m$ people that want to travel through the network. Each person starts from city 1ドル,ドル and has a specific destination city $d$ in mind. These people will line up in the given order. What is the maximum number of people you can route correctly to their destination if you close roads optimally?

입력

The first line of input contains two integers $n$ and $m$ (2ドル \le n,m \le 2 \times 10^5$), where $n$ is the number of cities and $m$ is the number of people.

Each of the next $n-1$ lines contains two integers $a$ and $b$ (1ドル \le a < b \le n$), denoting a directed road from city $a$ to $b$. These roads will describe a rooted tree with city 1ドル$ as the root.

Each of the next $m$ lines contains a single integer $d$ (2ドル \le d \le n$), denoting the destination city of the next person in line.

출력

Output a single integer, which is the maximum number of people you can route to the correct destination.

제한

힌트