题目详情题解（0）讨论（0）提交记录（0）

CFCF2196F.Indivisible

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定两个数字 nn 和 mm。

一张无向图被称为「美丽的」，当且仅当它满足以下条件：

  • 没有自环和重边。
  • 恰好有 nn 个顶点和 mm 条边。
  • 不存在一种将所有顶点划分为两个集合的方法，使得第一个集合内所有顶点的度数之和与第二个集合的度数之和相等。

现在请你判断，是否存在一张满足上述条件的美丽无向图。如果存在，请给出一种构造。

输入格式

每组测试包含多个测试用例。第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例数量。

之后每个测试用例占一行，每行包含两个整数 n,mn, m（12≤n≤105,1≤m≤min⁡(2⋅105,n(n−1)2)12 \leq n \leq 10^5, 1 \leq m \leq \min(2 \cdot 10^5, \frac{n(n-1)}{2})），表示无向图的顶点数和边数。

保证所有测试用例的 nn 之和不超过 10510^5，所有测试用例的 mm 之和不超过 2×1052 \times 10^5。

输出格式

对于每个测试用例：

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

输入输出样例

  • 输入#1

    5
12 7
12 1
90000 12
30 434
30 435

    输出#1

    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

说明/提示

在第一个测试用例中，图是一个有 77 个顶点的简单环。顶点的度数为 {2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0}\{2,\,2,\,2,\,2,\,2,\,2,\,2,\,0,\,0,\,0,\,0,\,0\}。显然，这样的图无法将顶点划分为两个度数和相等的部分。

在第二个测试用例中，由于 m=1m = 1，可以将顶点任意划分为两部分并让度数之和相等，因此不存在满足条件的图。

首页