AT_agc067_a.[AGC067A] Big Clique Everywhere

给定一个有 $N$ 个顶点、编号为 $1$ 到 $N$ 的简单无向图 $G$。$G$ 有 $M$ 条边，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

请判断 $G$ 是否满足以下条件：

• 对于顶点集合 $\{1,2,\cdots,N\}$ 的任意一个子集 $X$，都存在 $X$ 的子集 $Y$，使得 $|Y| \ge \frac{|X|}{2}$ 且 $Y$ 构成一个团（即 $Y$ 中任意两点之间都有边相连）。

有 $T$ 组测试数据需要判断。

输入从标准输入读入，格式如下：

$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 或 No 的输出不区分大小写。

限制条件

• $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$。
• 所有输入值均为整数。

样例解释 1

对于第 $1$ 个测试用例，$G$ 满足条件。在这种情况下，所有子集 $X$ 本身就是团，因此可以直接取 $Y=X$。
对于第 $2$ 个测试用例，$G$ 也满足条件。例如，对于 $X=\{2,3\}$，可以取 $Y=\{2\}$。
对于第 $4$ 个测试用例，$G$ 不满足条件。取 $X=\{1,2,3\}$ 时，没有满足条件的 $X$ 的子集 $Y$。

由 ChatGPT 4.1 翻译