Problem E
Evading a Monster

A monster is chasing you in a tree with $N$ vertices, labeled between $1$ and $N$. Initially, the monster starts at vertex $1$ and you start at vertex $2$. Through careful analysis of the monster’s hunting patterns you have concluded that it will move to the (not necessarily distinct) $M$ vertices $a_1$, $a_2$, $\dots $, $a_ M$ in order, where $a_ i$ and $a_{i+1}$ are adjacent in the tree for all $1 \le i \le M - 1$.

You are trying to keep away from the monster, while performing as few moves as possible. A move means moving from a vertex to an adjacent vertex. Before each of the monster’s moves, you may make any number of moves.

What is the minimal number of moves you have to make?


The first line contains the integers $N$ ($2 \le N \le 100\, 000$) and $M$ ($1 \le M \le 500\, 000$), the number of vertices in the tree and the number of moves the monster performs.

The next $N-1$ lines contains the edges of the tree. Each line consists of two integers $u$ and $v$ ($1 \le u \neq v \le N$), the vertices of the edge.

The final line contains the $M$ numbers $a_1, \dots , a_ M$, the vertices the monster moves through ($1 \le a_ i \le N$) in order. It is guaranteed that $a_ i$ and $a_{i+1}$ are adjacent vertices of the tree for $1 \le i \le M-1$, and that vertices $1$ and $a_1$ are adjacent.


Output a single integer, the minimal number of moves you have to perform to avoid the monster.

If avoiding the monster is impossible, output -1.


Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.






$N \le 100$, $M \le 500$



Each vertex has degree at most $3$.



No additional constraints.

Sample Input 1 Sample Output 1
4 2
1 2
2 3
1 4
2 3
Sample Input 2 Sample Output 2
5 7
1 2
2 3
1 4
2 5
2 3 2 5 2 1 4

Please log in to submit a solution to this problem

Log in