CF2196F Indivisible

给定两个数字 $n$ 和 $m$。 一张无向图被称为「美丽的」，当且仅当它满足以下条件： - 没有自环和重边。 - 恰好有 $n$ 个顶点和 $m$ 条边。 - 不存在一种将所有顶点划分为两个集合的方法，使得第一个集合内所有顶点的度数之和与第二个集合的度数之和相等。 现在请你判断，是否存在一张满足上述条件的美丽无向图。如果存在，请给出一种构造。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 之后每个测试用例占一行，每行包含两个整数 $n, m$（$12 \leq n \leq 10^5, 1 \leq m \leq \min(2 \cdot 10^5, \frac{n(n-1)}{2})$），表示无向图的顶点数和边数。 保证所有测试用例的 $n$ 之和不超过 $10^5$，所有测试用例的 $m$ 之和不超过 $2 \times 10^5$。

对于每个测试用例： - 如果不存在满足条件的美丽图，输出一行 "No"（不带引号）。 - 否则，输出一行 "Yes"，并在接下来的 $m$ 行中，每行输出一条边（两个用空格分隔的顶点编号，编号从 $1$ 到 $n$），描述这样一张美丽图。多种构造均可，按任意顺序输出。

在第一个测试用例中，图是一个有 $7$ 个顶点的简单环。顶点的度数为 $\{2,\,2,\,2,\,2,\,2,\,2,\,2,\,0,\,0,\,0,\,0,\,0\}$。显然，这样的图无法将顶点划分为两个度数和相等的部分。 在第二个测试用例中，由于 $m = 1$，可以将顶点任意划分为两部分并让度数之和相等，因此不存在满足条件的图。 由 ChatGPT 5 翻译