{"raw_statement":[{"iden":"statement","content":"给定一棵 $N$ 点的树，点编号为 $1$ 到 $N$，现在在 $K$ 个点上有羊，你的任务是在树上分配一些牧羊人。\n\n这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。\n\n当然，牧羊人可以和羊在同一个点上，但这样牧羊人只会看管这一个点上的那个羊。\n\n求一种牧羊人的分配方案使得牧羊人总数最小。"},{"iden":"input","content":"第一行两个整数 $N,K$ 代表树的点数和有羊的点数。         \n接下来 $N-1$ 行每行两个整数 $a_i,b_i$ 代表树的一条边。         \n第 $N+1$ 行 $K$ 个整数 $o_i$，代表有羊的点的编号。"},{"iden":"output","content":"第一行一个整数 $X$ 代表牧羊人总数的最小值。       \n第二行 $X$ 个整数代表每个牧羊人分配到哪个点上。         \n如果有多种解，输出一种即可。"},{"iden":"note","content":"#### 样例 3 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qwahnh8z.png)\n\n#### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n- Subtask 1（8 pts）：$1 \\le N \\le 5 \\times 10^5$，任意一个点 $i$ 都与 $i+1$ 相连（$1 \\le i \\le N-1$）。\n- Subtask 2（18 pts）：$1 \\le K \\le 15$，$1 \\le N \\le 5 \\times 10^5$。\n- Subtask 3（23 pts）：$1 \\le N \\le 2000$。\n- Subtask 4（51 pts）：$1 \\le N \\le 5 \\times 10^5$。\n\n对于 $100\\%$ 的数据，$1 \\le K \\le N$，$1 \\le a_i,b_i \\le N$，$1 \\le  o_i \\le N$。\n\n**本题使用 Special Judge，checker 提供者 @[Lynkcat](https://www.luogu.com.cn/user/120911)，感谢他的贡献。**\n\n#### 说明\n\n翻译自 [Croatian Olympiad in Informatics 2020 B Pastiri](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。"}],"translated_statement":null,"sample_group":[["4 2\n1 2\n2 3\n3 4\n1 4","2\n1 3"],["9 5\n1 2\n2 3\n3 4\n3 5\n1 6\n1 7\n7 8\n8 9\n2 5 6 7 9","3\n1 4 9"],["20 9\n1 2\n2 3\n2 4\n4 5\n4 6\n5 7\n7 8\n8 9\n7 10\n10 11\n6 12\n6 13\n6 17\n13 14\n14 15\n14 16\n17 18\n18 19\n18 20\n1 3 9 11 12 15 16 19 20","3\n5 14 18"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}