AT_tkppc4_2_b.Stalker

题目简述

给定一张 $N$ 点 $(N-1)$ 边的连通无向图（也就是一棵树），点的编号从 $1$ 到 $N$，第 $i$ 条边连接点 $A_i$ 和点 $B_i$。

你需要找到一条树上路径，使得其不会经过任意一个点两次及以上，且中途经过特定的 $M$ 个点 $C_1,C_2,...,C_M$ 各一次（顺序任意）。你可以任意选定这条路径的起点和终点。

请问：是否能找到上面所述的那条树上路径？如果能，请输出 Yes，否则请输出 trumpet。

一句话题意：给定一棵 $N$ 个节点的树，问 $C_1,C_2,…,C_M$ 这 $M$ 个点是否在同一条链上。

第一行输入两个整数 $N,M$。

第二行到第 $N$ 行，第 $(i+1)$ 行输入两个整数 $A_i,B_i$。

第 $(N+1)$ 行输入 $M$ 个整数 $C_1,C_2,...,C_M$。

若存在此种路径，请输出 Yes；否则，请输出 trumpet。

输入输出样例

输入 #1

3 2
1 2
1 3
1 2

输出 #1

Yes

输入 #2

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

输出 #2

Yes

输入 #3

4 3
1 2
1 3
1 4
2 3 4

输出 #3

trumpet

样例 #1 解释

路径为 $1-2$。

样例 #2 解释

路径为 $3-4-5$。

样例 #3 解释

不存在满足要求的路径。

数据规模与约定

本题在 AT 上满分 $400$。对于全部测试点，保证 $1\le N\le 10^5$，$1\le A_i,B_i\le N$，$1\le M\le N$，$1\le C_i\le N$，当 $i\neq j$ 时 $C_i\neq C_j$，给定的图构成一棵树。

对于前 $200$ 分的测试点，保证 $N\le 2000$。对于后 $200$ 分的测试点，无特殊限制。