问题 1521 --热浪Ⅱ

1521: 热浪Ⅱ

时间限制: 2 Sec  内存限制: 128 MB
提交: 109  解决: 15
[提交][状态][讨论版][命题人:]

题目描述

Famer John正在向德克萨斯州纯朴的民众们运送大量的营养冰凉的牛奶,以减轻德克萨斯人忍受酷暑的痛苦。目前Famer John正在通过一片广袤的荒原,这里有 N 个小镇,小镇间有着N-1条公路连接,保证小镇间的居民可以正常往来。

Famer John需要驾车依次通过 M 个特定的小镇,将牛奶送给居民,而他将从编号为1的小镇出发。假设通过每条小镇间的公路所需要的时间都相同,求Famer John完成牛奶运送任务,最少需要通过多少条公路?

输入

第一行包含两个正整数NM

接下来N-1行,每行包含两个正整数u,v,表示编号为u的小镇到编号为v的小镇之间存在一条公路;

接下来一行有M个正整数m,按顺序描述M个目标小镇。


输出

输出一个整数,表示从1号小镇出发顺次经过M个小镇所需要通过的最少的公路数目。

样例输入

5 4
1 2
1 5
3 5
4 5
1 3 2 5

样例输出

7

提示


对于40%的数据,保证2 <= N <= 1000,1 <= M <= 500;



对于80%的数据,保证2 <= N <= 5000,1 <= M <= 500;



对于100%的数据,保证2 <=  N <= 20000,1 <= M <= 1000,2 <= u, v ,m<= N;

来源

 

[提交][状态]