Laminar Set Family on Trees

In combinatorial optimization, a subset family \(F\) of some set \(\Omega\) is called laminar if and only if it does not contain the empty set and for any two distinct sets \(A, B \in F\), one of the following holds: \(A \subset B\), \(B \subset A\), or \(A \cap B = \emptyset\).

Lucas, an experienced problem setter, combines the concept of laminar sets with trees to form a programming problem. You are given an undirected tree with \(n\) vertices and a family \(F = \{F_1, F_2, \dots, F_k\}\) of sets. Each set \(F_i\) is defined as the set of all vertices on the unique simple path between two given vertices \(a_i\) and \(b_i\) in the tree. In this context, \(\Omega = V\) and each \(F_i \subseteq V\).

Your task is to check whether the family \(F\) is laminar.

Laminar Condition

• None of the sets is empty.
• For every two distinct sets \(F_i\) and \(F_j\), it must hold that either \(F_i \subset F_j\), \(F_j \subset F_i\), or \(F_i \cap F_j = \emptyset\).

If the family meets the above conditions, output Yes, otherwise output No.

inputFormat

The first line contains two integers \(n\) and \(k\) \( (2 \leq n, k \leq 10^5)\) representing the number of vertices in the tree and the number of queries respectively.

Then \(n-1\) lines follow, each containing two integers \(u\) and \(v\) \(1 \leq u,v \leq n\) which denote an undirected edge between vertices \(u\) and \(v\). It is guaranteed that the given edges form a tree.

After that, there are \(k\) lines, each containing two integers \(a_i\) and \(b_i\) \(1 \leq a_i, b_i \leq n\). They represent that the set \(F_i\) consists of all vertices on the unique simple path between \(a_i\) and \(b_i\) in the tree.

outputFormat

Output a single line: Yes if the family \(F\) is laminar; otherwise, output No.

sample

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

Yes