题目描述
In the thriving city, various industries are fueled by the extensive utilization of different liquids. The metropolis houses $n$ unique types of liquids, each with specific characteristics and applications ranging from energy to pharmaceuticals.
The Center for Chemical and Physical Combinations (CCPC) plays a pivotal role in researching and categorizing these liquids. A crucial part of their research focuses on understanding the miscibility relations among the liquids. They have identified $m$ pairs of miscibility relations, each pair representing two types of liquids that are miscible (mutually soluble).
However, miscibility is not always a straightforward property. It exhibits a transitive relation, meaning if liquid type $A$ is miscible with type $B$, and type $B$ is miscible with type $C$, then type $A$ will also be miscible with type $C$.
Whether developing a new kind of fuel or a groundbreaking medical serum, the right combination of liquids is paramount. An incorrect mixture could lead to immiscible components, which could be ineffective or even dangerous. Therefore, if it is not possible to deduce that two types of liquids are miscible based on the given miscibility relations and their transitivity, then those two types of liquids are considered immiscible.
The industries often require the creation of substances involving a specific set of $k$ types of liquids, all of which must be miscible. Your role as a computational scientist at CCPC is to develop an algorithm that will efficiently determine if a given set of $k$ types of liquids are miscible. Specifically, for any two distinct types of liquids within this set of $k$ types, if they are all miscible with each other, then the $k$ types of liquids are considered to be miscible.
The Center for Chemical and Physical Combinations (CCPC) plays a pivotal role in researching and categorizing these liquids. A crucial part of their research focuses on understanding the miscibility relations among the liquids. They have identified $m$ pairs of miscibility relations, each pair representing two types of liquids that are miscible (mutually soluble).
However, miscibility is not always a straightforward property. It exhibits a transitive relation, meaning if liquid type $A$ is miscible with type $B$, and type $B$ is miscible with type $C$, then type $A$ will also be miscible with type $C$.
Whether developing a new kind of fuel or a groundbreaking medical serum, the right combination of liquids is paramount. An incorrect mixture could lead to immiscible components, which could be ineffective or even dangerous. Therefore, if it is not possible to deduce that two types of liquids are miscible based on the given miscibility relations and their transitivity, then those two types of liquids are considered immiscible.
The industries often require the creation of substances involving a specific set of $k$ types of liquids, all of which must be miscible. Your role as a computational scientist at CCPC is to develop an algorithm that will efficiently determine if a given set of $k$ types of liquids are miscible. Specifically, for any two distinct types of liquids within this set of $k$ types, if they are all miscible with each other, then the $k$ types of liquids are considered to be miscible.
输入
The first line contains an integer $T$ ($1 \leq T \leq 20$), representing the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \leq n,m \leq 10^5$), representing the total number of liquids and the number of solubility relations, respectively.
Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \leq u,v \leq n$, $u \neq v$), where $u$ and $v$ represent the types of two liquids that are mutually soluble.
The following line contains a single integer $k$ ($1 \leq k \leq n$), indicating the number of liquids being considered.
The last line of each test case includes $k$ different integers within $[1,n]$, each denoting a type of liquid
The first line of each test case contains two integers $n$ and $m$ ($1 \leq n,m \leq 10^5$), representing the total number of liquids and the number of solubility relations, respectively.
Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \leq u,v \leq n$, $u \neq v$), where $u$ and $v$ represent the types of two liquids that are mutually soluble.
The following line contains a single integer $k$ ($1 \leq k \leq n$), indicating the number of liquids being considered.
The last line of each test case includes $k$ different integers within $[1,n]$, each denoting a type of liquid
输出
For each test case, output a single line containing either $\texttt{YES}$ if all $k$ types of liquids are mutually soluble, or $\texttt{NO}$ if they are not.
样例输入 Copy
3
3 2
1 2
1 3
3
1 2 3
4 2
1 2
3 4
3
1 2 4
6 4
1 2
3 4
5 6
1 5
2
1 6
样例输出 Copy
YES
NO
YES