CF2172N New Kingdom

在即将上线的策略游戏 Island Cartographer: Penultimate Chapter（ICPC）中，玩家将扮演被帝国制图与规划理事会雇佣的桥梁工程师，为遍布于群岛上的新王国设计交通网络。为了兼顾稳定与探索，理事会要求玩家的规划必须严格遵循以下规则。 第一个也是基本的要求是，王国的交通网络必须是简单连通的。也就是说，每条堤道连接的是两个不同的岛屿，不存在两个堤道连接相同的岛屿对，并且对于任意一对不同的岛屿，存在由若干堤道组成的通路可以相互到达。 理事会听说了古老的旅行者欧拉（Euler）的智慧，有些游客可能会尝试用仅经过每个堤道一次的方式游览所有堤道。如果做得到，这次旅游就太匆忙了。为让他们路程更长，理事会的第二个要求是，必须恰好有 $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"。 否则，首行输出 "Yes"。第二行输出一个整数 $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 \ne v_i$ - 对所有 $i \ne j$，$\{u_i, v_i\} \ne \{u_j, v_j\}$ 可以证明，对于任意有解的输入，都存在一个满足这些限制的解。

由 ChatGPT 5 翻译