计划

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file plan.in Output file plan.out




【问题描述】

SY战队的首领SYS最近几天很烦恼,SY战队想要继续开发新小陆,SYS必须马上制定出开发计划。新小陆可开发区域位于一片沼泽地中,数目不明,DD战队可以随便选择一个进行开发。SYS已经得到了前往沼泽地的地图,他可以清晰地看到自己所在的总部位于1号已开发区域,并且知道由1号已开发区域可以到达的每一片区域以及这些可以到达的区域可以到达的区域。这些区域包括已开发的和未开发(可开发)的,共有n个,每一个区域都有一个固定编号,从1~n;而且整个小陆刚好有n-1条路径。由一个区域到达另一个区域需要一天,并且到达这个新的区域后不会再返回。

虽然不知道新小陆可开发区域的具体位置,但是DDS知道它们有共同的特征:一旦进入将无路可走,即没有新的区域可以到达。有的区域比较贫瘠,称之为P区域,在P区域会因为各种问题不得不逗留一天,然后才能继续前进;假如可开发区域也是P区域,那么逗留几天显然不是问题,可开发区域和其他可开发区域等价。

知道这些并不能完全解决SYS的烦恼,由于SY战队的成员智商很低,到达一个区域后不知道权衡利弊,总是随便选择一个新的可以到达的区域前进,所以他们可能走了很久才到达一个可开发区域。

SY战队当然想尽量节省物资,所以战队只能提供足够m天使用的物资。DDS想知道他的队员们最不可能到达和最可能到达的可开发区域的编号,假如有多个地区情况类似,两个答案都输出编号最小的。

【输入格式】

第一行三个数,n,m,k。分别表示区域数目,物资可以承受的天数和P区域的数目;

第二行k个数(若k≠0),表示P区域的编号;

接下来n-1行,每行两个数表示相连的区域的编号。

【输出格式】

输出两行,第一行表示最不可能到达的可开发区域,第二行表示最可能到达的可开发区域。

【输入样例】

6 1 0
1 2
1 3
2 4
2 6
4 5 

【输出样例】

5
3

【数据范围】

20%数据:2≤n<=20 ,2≤m≤50 ,0≤k≤5

100%数据:2≤n≤1000,2≤m≤1000; 0≤k≤100