← 返回题目
题库练习 Indivisible
← 上一题 下一题 →

A16707 | Indivisible

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定两个数字 $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$），描述这样一张美丽图。多种构造均可，按任意顺序输出。

输入输出样例

输入 #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
C++ 编辑器
输入
输出