#P18492. Dense Planting

Dense Planting

Dense Planting

给定整数 KK,构造一个满足以下条件的无向图:

  • 顶点数 NN 满足 1≤N≤1001\le N\le100;
  • 边数 MM 至多为 10001000;
  • 每条边都视为可以区分的不同边时,图恰好有 KK 棵生成树。换句话说,在从 MM 条边中选取一些边并删除其余边的 2M2^M 种方式中,恰有 KK 种方式能使剩余的边构成一棵树。

输入只包含一行,一个整数 KK,其中 1≤K≤1091\le K\le10^9。

输出任意一个符合条件的无向图,格式为:

N M
U_1 V_1
...
U_M V_M

第 ii 行端点 Ui,ViU_i,V_i 表示第 ii 条边连接的两个顶点,顶点编号为 11 至 NN。允许重边,同一对端点之间的不同边仍是可区分的边。若有多个答案,可以输出任意一个。

样例一输入:

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

第一组样例的输出图如下:

原样例一的多重图

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

原题展示的一棵生成树

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