Famer John正在向德克萨斯州纯朴的民众们运送大量的营养冰凉的牛奶,以减轻德克萨斯人忍受酷暑的痛苦。目前Famer John正在通过一片广袤的荒原,这里有 N 个小镇,小镇间有着N-1条公路连接,保证小镇间的居民可以正常往来。
Famer John需要驾车依次通过 M 个特定的小镇,将牛奶送给居民,而他将从编号为1的小镇出发。假设通过每条小镇间的公路所需要的时间都相同,求Famer John完成牛奶运送任务,最少需要通过多少条公路?
Famer John正在向德克萨斯州纯朴的民众们运送大量的营养冰凉的牛奶,以减轻德克萨斯人忍受酷暑的痛苦。目前Famer John正在通过一片广袤的荒原,这里有 N 个小镇,小镇间有着N-1条公路连接,保证小镇间的居民可以正常往来。
Famer John需要驾车依次通过 M 个特定的小镇,将牛奶送给居民,而他将从编号为1的小镇出发。假设通过每条小镇间的公路所需要的时间都相同,求Famer John完成牛奶运送任务,最少需要通过多少条公路?
第一行包含两个正整数N,M
接下来N-1行,每行包含两个正整数u,v,表示编号为u的小镇到编号为v的小镇之间存在一条公路;
接下来一行有M个正整数m,按顺序描述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;