分数: 600 点
问题陈述
给你一个简单的无向图 G 与 N 顶点编号 1 to N. G 有 M 边缘和 i第一条边连接顶点 A_i 和 B_i.
检查是否 G 满足以下条件:
- 对于每个子集 顶点集的 X 顶点集的 \{1,2,\cdots,N\},存在一个子集 Y of X 这样 |Y|\ge \frac{|X|}{2} 和 Y 形成一个派系。
你有 T 要解决的测试用例。
约束
- 1\le T \le 10^3
- 1\le N \le 10^5
- 0 \le M \le 10^6
- 1 \le A_i,B_i \le N
- 给定的图不包含自环或多重边。
- 总和 N 单个输入中的测试用例最多 10^5.
- 总和 M 单个输入中的测试用例最多 10^6.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例均按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
对于每个测试用例,如果 G 满足条件,打印 Yes,否则打印 No.
打印中 Yes or No,您可以以任何大小写(大写或小写)输出每个字母。
示例输入 1
4 3 3 1 2 1 3 2 3 3 2 1 2 1 3 3 1 1 2 3 0
示例输出 1
Yes Yes Yes No
对于 1-st 测试用例, G 满足条件。 在这种情况下,每个子集 X 是一个派系,所以我们可以让 Y=X.
对于 2-nd 测试用例, G 满足条件。 例如,对于 X=\{2,3\},我们可以让 Y=\{2\}.
对于 4- 第一个测试用例, G 不满足条件。 如果我们让 X=\{1,2,3\},没有子集 Y of X 满足条件。