The Squirrel in the Tree

Interview

Time limit4sMemory limit1024 MB

Summary

Given a tree rooted at node 1 and a set of nodes holding nuts, find the shortest round trip from node 1 that visits every nut node.

Level: Medium5 of 10
Topics: Tree, DFS, Graph, Greedy
Solved: No attempts yet

Problem

A squirrel lives in a tree with $N$ nodes and $N-1$ edges. Each edge has length 1 and connects two nodes. The squirrel has hidden nuts in some of the nodes and now wants to collect them. If the squirrel starts at node 1 (the root of the tree), what is the shortest distance it must travel to fetch all the nuts and return to node 1? The squirrel can carry several nuts at the same time.

It is guaranteed that any pair of nodes can be reached by walking along a sequence of edges.

Input

The first line contains two integers $N$ and $K$ ( $1 \le K \le N \le 100\,000$ ), the number of nodes in the tree and the number of nodes with nuts. The second line contains $K$ distinct integers, the nodes where the squirrel has hidden nuts. Nodes are indexed 1 to $N$ . Then follow $N-1$ lines. Each line contains two integers $1 \le a, b \le N$ , meaning there is an edge between node $a$ and node $b$ .

Output

Print one integer: the shortest distance the squirrel must travel to fetch all the nuts.

Examples2

Example 1
Input
```
5 2
4 5
1 2
2 3
2 4
1 5
```
Expected output
```
6
```

Example 2

Input

Expected output