#P18492. Dense Planting
Dense Planting
Dense Planting
给定整数 ,构造一个满足以下条件的无向图:
- 顶点数 满足 ;
- 边数 至多为 ;
- 每条边都视为可以区分的不同边时,图恰好有 棵生成树。换句话说,在从 条边中选取一些边并删除其余边的 种方式中,恰有 种方式能使剩余的边构成一棵树。
输入只包含一行,一个整数 ,其中 。
输出任意一个符合条件的无向图,格式为:
N M
U_1 V_1
...
U_M V_M
第 行端点 表示第 条边连接的两个顶点,顶点编号为 至 。允许重边,同一对端点之间的不同边仍是可区分的边。若有多个答案,可以输出任意一个。
样例一输入:
11
样例一输出:
3 6
1 2
1 3
1 3
2 3
2 3
2 3
样例二输入:
54
样例二输出:
4 10
1 2
2 3
2 3
2 3
3 4
3 4
3 4
4 1
4 1
4 1
第一组样例的输出图如下:

按生成树使用的两类端点对分类:同时选用 与 的边有 2 种;同时选用 与 的边有 3 种;同时选用 与 的边有 6 种。因此生成树总数为 。下图红边展示其中一棵生成树:

下面的图也恰有 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