← 返回题目列表

AtCoder · agc067_a

A. 大集团无处不在

中文机器翻译题面 查看原题

分数: 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 满足条件。