题目描述

While studying combinatorial optimization, Lucas came across the notion of laminar set family. A subset family $F$ of some set $Ω$ is called laminar if and only if it does not contain an empty set and for any two distinct sets A , $B ∈ F$ it is correct that either $A ⊂ B$ or $B ⊂ A$ or $A ∩ B = ∅$.

As an experienced problem setter Lucas always tries to apply each new piece of knowledge he gets as an idea for a programming competition problem. An area of his scientific interests covers recognition problems that usually sound like Given some weird combinatorial property, check if the given structure satisfies it.

Lucas believes that the perfect programming competition problem should contain a cactus a tree in it. Trying to put together laminar sets and trees into a recognition problem, he finally came up with the following problem: given an undirected tree on $n$ vertices and a family $F = {F_{1}, . . . , F_{k}}$ of sets, where $F_{i}$ consists of all vertices belonging to the simple path between some two vertices $a_{i}$ and $b_{i}$ of the tree, check if the family $F$ is a laminar family. Note that in this case $Ω = V$ , and each $F_{i} ⊆ V$ .

As you can see, Lucas had succeeded in suggesting this problem to the programming contest. Now it is up to you to solve it.

输入格式

The first line of the input contains two integers $n$ and $f (1 \le n , f \le 100 000)$ -- the number of vertices in the tree and the number of elements in a family $F$ .

Next $n−1$ lines describe the tree structure. In the i-th line there are two integers $u_{i}$ and $v_{i} (1 \le u_{i}, v_{i} \le n , u_{i} ≠ v_{i})$ -- the indices of the vertices that are connected by the i-th edge of the tree.

Next $f$ lines describe the sets forming the family $F$ . In the i-th line there are two integers $a_{i}$ and $b_{i} (1 \le a_{i}, b_{i} \le n)$ , such that $F_{i}$ consists of all vertices belonging to the simple path between vertices $a_{i}$ and $b_{i}$ in the tree (including $a_{i}$ and $b_{i}).$

输出格式

Output the only word Yes or No depending on whether or not the given set family is laminar.

题目大意

• 给定一棵 $n$ 个节点的树，给出 $f$ 条树上的路径，试判断下面的命题是否成立：
• $f$ 条路径中，任意两条路径的点集的交集为空，或者一个是另一个的子集。
• 成立输出 Yes，不成立输出 No。
• $1 \leq n,f \leq 10^5$

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

No

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

Yes

提示

Time limit: 2 s, Memory limit: 512 MB.