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 翻译