Given a connected tree with \(N\) vertices and \(N-1\) edges, you must answer \(M\) queries of the type:
- given three unique vertices \(A\), \(B\), and \(C\), find if there exists a simple path that contains all three vertices.
Note: A simple path is a path in a tree that does not have repeating vertices.
Input format
- The first line contains a single integer \(T\), which denotes the number of test cases.
- For each test case:
- The first line contains \(N\) denoting the number of vertices in the tree.
- The next \(N-1\) lines contain 2 space-separated integers, \(u\) and \(v\), indicating that there is an edge between vertices \(u\) & \(v\).
- The next line contains \(M\) denoting the number of queries.
- The next \(M\) lines contain 3 unique space-separated integers, \(A\), \(B\), and \(C\).
Output format
For each test case, answer all the \(M\) queries. For each query print \(\text{Yes}\) if there exists a simple path that contains all three vertices \(A\), \(B\), and \(C\), otherwise print \(\text{No}\). Print answer for each query in a new line.
Constraints
\(1 \leq T \leq 10^5 \\ 3 \leq N \leq 2×10^5 \\ 1≤u,v≤N\\ \\ 1 \leq M \leq 2×10^5\\ 1≤A, B, C≤N\ \\ \text{The sum of all values of N over all test cases doesn't exceed } 2×10^5 \\ \text{The sum of all values of M over all test cases doesn't exceed } 2×10^5\)
The first line denotes T = 1.
For test case \(1\):
We are given:
- N = 5
- M = 3
Now,
- For the first query, we have a simple path as \(1 → 2 → 5 → 3\), which contains all the three vertices 3, 1, and 2. Therefore the answer is \(\text{Yes}\).
- For the Second query, we have a simple path as \(4 → 2 → 5 → 3\), which contains all the three vertices 2, 3, and 4. Therefore the answer is \(\text{Yes}\).
- For the third query, there exists no simple path in the given tree which contains all the three vertices 1, 3, and 4. Therefore the answer is \(\text{No}\).
