问题 G: Solubility
内存限制:256 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
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 first line contains an integer T (1 ≤ T ≤ 20), representing the number of test cases.
The first line of each test case contains two integers n and m (1 ≤ n, m ≤ 105
), 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 ≤ u, v ≤ n, u 6= v), where u and v represent
the types of two liquids that are mutually soluble.
The following line contains a single integer k (1 ≤ k ≤ 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 YES if all k types of liquids are mutually soluble,
or NO if they are not.
样例输入 复制
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
样例输出 复制
YES
NO
YES