AT_agc071_c.[AGC071C] Orientable as Desired

给定一个简单连通无向图 $G$，包含编号为 $1, 2, \dots, N$ 的 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

请判断是否存在满足以下所有条件的长度为 $N$ 的非负整数序列 $X = (X_1, X_2, \dots, X_N)$：

• 对于每个 $v = 1, 2, \dots, N$，$X_v$ 不超过图 $G$ 中顶点 $v$ 的度数
• 不存在一种对 $G$ 的 $M$ 条边进行定向的方法，使得得到的有向图中每个顶点 $v$ 的入度或出度等于 $X_v$

给定 $T$ 个测试用例，请对每个用例输出答案。

输入从标准输入按以下格式给出：

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出 $T$ 行。第 $i$ 行对应第 $i$ 个测试用例的结果：若存在符合条件的 $X$ 则输出 Yes，否则输出 No。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $N - 1 \leq M \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 输入均为整数
• 输入的图 $G$ 是简单连通无向图
• 单个输入文件中所有测试用例的 $N$ 总和不超过 $2 \times 10^5$
• 单个输入文件中所有测试用例的 $M$ 总和不超过 $2 \times 10^5$

样例解释 #1

对于第一个测试用例，例如 $X = (2, 2, 2, 1)$ 满足条件。
对于第二个测试用例，不存在满足条件的 $X$。

翻译由 DeepSeek R1 完成