← 返回题目列表

Codeforces · 2196/F

F. 不可分割

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

给你两个数字 $$$n$$$ 和 $$$m$$$。

无向图称为 美丽 如果满足以下条件:

  • 它没有循环或多重边缘。
  • 它恰好有 $$$n$$$ 个顶点和 $$$m$$$ 个边。
  • 它的顶点 不能 被分为 $$$2$$$ 集合,使得第一个集合中所有顶点的度数之和与第二个集合中所有顶点的度数之和相等。

您需要报告 美丽 给定 $$$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 \cdot 10^5$$$。

输出

对于每个测试用例,输出 “否” 如果这样的图不存在。否则,输出 “是”,然后在接下来的 $$$m$$$ 行中 - 的边缘 美丽 任意顺序的图表。如果有多个答案,您可以输出其中任何一个。

示例

输入
复制

5
12 7
12 1
90000 12
30 434
30 435

输出
复制

Yes
1 2
2 3
3 4
4 5
5 1
1 3
2 4
No
Yes
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
No
No

注意

在第一个测试用例中,该图是 $$$7$$$ 个顶点的简单循环。顶点的度数为 $$$\{2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0\}$$$。很容易看出,在这样的图中,不可能将顶点分成度数相等的$$$2$$$部分。

在第二个测试用例中,由于 $$$m = 1$$$,很容易看出顶点总是可以分为度数相等的 $$$2$$$ 部分。因此,不存在解决方案。