AT_ttpc2023_k Dense Planting

给定一个整数 $K$，请构造一个无向图，使其满足以下条件，并且边的数量尽可能少。 - 顶点数 $N$ 满足 $1 \le N \le 100$。 - 边数 $M$ 满足 $M \le 10^5$。 - 当所有的边都互相区分时，图中恰好存在 $K$ 个不同的生成树。也就是说，从 $M$ 条边中选择若干条边的方法共有 $2^M$ 种，其中恰好有 $K$ 种选择能够使剩下的边组成一棵树。

输入通过标准输入按如下格式给出。 > $K$

输出满足条件的无向图，要求按如下格式输出。若存在多个满足条件的图，输出其中任意一个均可。 > $N$ $M$ > $U_1$ $V_1$ > $\vdots$ > $U_M$ $V_M$ 其中 $U_i, V_i\ (1 \le i \le M)$ 表示第 $i$ 条边连接了顶点 $U_i$ 和顶点 $V_i$。

### 得分 当程序对所有测试用例均输出满足题意要求时，该提交将被判定为 AC。此时，所有测试点中 $M$ 的最大值为 $M_{\max}$，评分标准如下： 条件 得分 $10^4 < M_{\max} \le 10^5$ 20分 $10^3 < M_{\max} \le 10^4$ 60分 $M_{\max} \le 10^3$ 100分 ### 样例解释 1 输出的图如下图所示：  例如，选择下述 $2$ 条边就可以构成该图的一棵生成树：  - 由边 $1 - 2$ 和边 $1 - 3$ 构成的生成树有 $2$ 种。 - 由边 $1 - 2$ 和边 $2 - 3$ 构成的生成树有 $3$ 种。 - 由边 $1 - 3$ 和边 $2 - 3$ 构成的生成树有 $6$ 种。 因此，总共存在 $11$ 个生成树。 另外，以下这样的图同样存在 $11$ 个生成树，因此，下述输出同样视为正确。  ``` 2 11 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ``` ### 数据范围 - $K$ 是整数。 - $1 \le K \le 10^9$。 由 ChatGPT 5 翻译