← 返回题目列表

Codeforces · 2172/N

N. 新王国

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

在即将推出的策略游戏中 岛屿制图师:倒数第二章 (ICPC),玩家扮演受雇于桥梁工程师的角色 帝国制图与规划委员会 设计一个横跨由堤道网络连接的 $$$n$$$ 群岛组成的新王国。为了实现稳定性和探索之间的平衡,理事会要求玩家的计划满足几项严格的规则。

第一个也是基本的要求是王国必须是 简单 和 已连接。也就是说,每条堤道连接两个不同的岛屿,没有两条堤道连接同一对岛屿,并且对于每对不同的岛屿,它们之间存在一条使用一系列堤道的路线。

在学习了传奇旅游者欧拉的古老智慧后,一些游客也许能够在一次无缝的旅行中准确地穿越每条堤道一次。如果这是可能的,那么那些游客将没有足够的时间来享受他们的旅行。为了让他们旅行的时间更长,委员会的第二个要求是 正好 $$$k$$$ 岛屿有奇数条堤道与其相连。

考虑了一些堤道 至关重要 到王国。如果拆除堤道会使某些岛屿之间的旅行变得不可能,那么堤道就至关重要。这些堤道对于当地发展、文化认同和旅游业很重要,但过多可能会导致交通拥堵。因此,议会的第三个也是最后一个要求是王国必须包含 正是 $$$b$$$ 重要的堤道。

要完成 ICPC 游戏,玩家必须提交一份建造堤道的计划,该计划满足理事会提供的参数 $$$n$$$、$$$k$$$ 和 $$$b$$$ 的所有要求。在游戏发布之前,您的任务是通过作为玩家设计有效的王国计划来测试游戏。如果游戏无法完成,请报告。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量$$$t$$$。测试用例的描述如下。

每个测试用例的唯一一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$b$$$,分别代表岛屿数量、连接奇数条堤道的岛屿的确切数量以及重要堤道的确切数量。

  • $$$1\le n\le 10^5$$$
  • $$$0\le k \le n$$$
  • $$$0\le b \le n-1$$$
  • 所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果没有符合有效计划要求的解决方案,则输出“No”在一行中。

否则,输出“是”在第一行。然后,在第二行输出一个整数$$$m$$$,表示您的计划中堤道的数量。在接下来的 $$$m$$$ 行中,输出两个由空格分隔的整数 $$$u_i$$$ 和 $$$v_i$$$,这意味着岛屿 $$$u_i$$$ 和 $$$v_i$$$ 通过一条堤道连接。如果有多个有效计划,则输出任意一个。

您的输出必须满足:

  • $$$0\le m\le 5n$$$
  • 对于所有 $$$1\le i\le m$$$、$$$1\le u_i、v_i\le n$$$。
  • 对于所有$$$1\le i\le m$$$,$$$u_i\neq v_i$$$。
  • 对于所有 $$$i\neq j$$$、$$$\{u_i, v_i\}\neq \{u_j, v_j\}$$$。
可以证明,对于每个可能有解的输入,都存在一个满足这些约束的解。

示例

输入
复制

4
6 2 1
3 1 2
4 0 0
5 4 2

输出
复制

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