[Solution] Passable Paths (easy version) Codeforces Solution

G1. Passable Paths (easy version)

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

This is an easy version of the problem. The only difference between an easy and a hard version is in the number of queries.

Polycarp grew a tree from n$n$ vertices. We remind you that a tree of n$n$ vertices is an undirected connected graph of n$n$ vertices and n−1$n-1$ edges that does not contain cycles.

He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).

In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

For example, for a tree below sets {3,2,5}$\{3,2,5\}$, {1,5,4}$\{1,5,4\}$, {1,4}$\{1,4\}$ are passable, and {1,3,5}$\{1,3,5\}$, {1,2,3,4,5}$\{1,2,3,4,5\}$ are not.

Polycarp asks you to answer q$q$ queries. Each query is a set of vertices. For each query, you need to determine whether the corresponding set of vertices is passable.

Input

The first line of input contains a single integer n$n$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$) — number of vertices.

Round Down the Price Codeforces Solution

Polycarp Writes a String from Memory Codeforces Solution

Train and Queries Codeforces Solution

Not a Cheap String Codeforces Solution

Split Into Two Sets Codeforces Solution

Equate Multisets Codeforces Solution

Passable Paths (easy version) Codeforces Solution

Passable Paths (hard version) Codeforces Solution

Following n−1$n-1$ lines a description of the tree..

Each line contains two integers u$u$ and v$v$ (1≤u,v≤n$1\le u,v\le n$, u≠v$u\ne v$) — indices of vertices connected by an edge.

Following line contains single integer q$q$ (1≤q≤5$1\le q\le 5$) — number of queries.

The following 2⋅q$2\cdot q$ lines contain descriptions of sets.

The first line of the description contains an integer k$k$ (1≤k≤n$1\le k\le n$) — the size of the set.

The second line of the description contains k$k$ of distinct integers p1,p2,…,pk$p_1,p_2,\dots ,p_k$ (1≤pi≤n$1\le p_i\le n$) — indices of the vertices of the set.

It is guaranteed that the sum of k$k$ values for all queries does not exceed 2⋅105$2\cdot {10}^5$.

Output

Output q$q$ lines, each of which contains the answer to the corresponding query. As an answer, output "YES" if the set is passable, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).