在即将推出的策略游戏中 岛屿制图师:倒数第二章 (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