问题 4885 --2.连通子图

4885: 2.连通子图

题目描述

  给定正整数 $k$,求构造一棵树,使得包含了 $1$ 号点的连通子图个数恰好为 $k$。
连通子图就是点集的一个子集(可以为全集),使得该点集中任意两个点均可以经过该点集中的点相互到达。

输入

本题每个测试点中包含多组数据。
多行,每行一组数据。对于每组数据,一行一个正整数 $k$。

输出

输出多行,对于每组数据:

第一行输出数 $n$ 表示树的点数。
接下来输出 $n-1$ 行,每行两个数 $u$ 和 $v$,用空格隔开,表示编号为 $u$ 的点和编号为 $v$ 的点之间有一条树边,编号从 $1$ 开始。

相邻两组数据的答案不需要任何空行隔开。

输入保证答案一定存在,你输出的 $n$ 必须是正整数且不得超过 $60$。对每个询问,你只需要输出任意一个合法解即可。

样例输入输出

输入#1 复制
6
输出#1 复制
4
2 3
1 2
1 4
输入#2 复制
16
输出#2 复制
5
1 2 
1 3
1 4
1 5

提示

对于 $20\%$ 的数据,$k \leq 60$。
另有 $20\%$ 的数据,只有一组询问且这个询问中的 $k=118$。
另有 $20\%$ 的数据,只有一组询问且这个询问中的 $k=536870912$。
另有 $20\%$ 的数据,只有一组询问且这个询问中的 $k=14007$。。
另有 $20\%$ 的数据,$k \leq 10^5$。
对于 $20\%$ 的数据,$1 \leq k \leq 10^9$,数据组数在 $1$ 到 $1000$ 之间。

序号 标题 作者 发表时间 费用 订购数 操作