题目描述

小明在某个游戏中要设计一个公园。

这个公园可以看成是一幅$n$个点，$m$条有向边的简单有向无环图（没有重边，没有自环）。

小明指定$1$号点作为起点，$n$号点作为终点。

小明的需求是：他需要让这幅图从起点到终点的方案数，恰好是$K$种。

请帮助小明设计这样一幅图吧。

输入格式

输入一个参数$K$。

输出格式

首先输出$n,m$，表示点数，边数。

请注意，你必须保证你输出的$n\leq 91,m\leq 230$

然后输出$m$行，每行$u,v(1\leq u<v\leq n)$表示一条有向边。

可以证明有向无环图一定存在一种编号方式满足，所有的边都是从编号小的连接到编号大的。

样例输入 #1

2

样例输出 #1

3 3
1 2
2 3
1 3

样例解释 #1

一共两条路：$(1,2,3),(1,3)$。

样例输入 #2

3

样例输出 #2

4 5
1 2
2 3
3 4
1 3
2 4

样例解释 #2

一共三条路：$(1,2,4),(1,2,3,4),(1,3,4)$。

数据范围

请注意，你必须保证你输出的$n\leq 91,m\leq 230$。

对于10%的数据：$K\leq 85$。

对于30%的数据：$K<2^9$。

对于50%的数据：$K<2^{30}$。

对于70%的数据：$K<2^{45}$。

对于80%的数据：$K<2^{46}$。

对于100%的数据：$K<2^{62}$。

以下是你可以用到的checker，出题人多么良心啊，给大家省去了宝贵的$1$分钟。

#include<bits/stdc++.h>
#define maxn 105
#define ll long long
using namespace std;
int n,m,u,v;
basic_string<int> edge[maxn];
ll dp[maxn];
map<int,int> vis;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++) 
	{
		cin>>u>>v; 
		assert(u<v); assert(vis[u*177+v]==0); 
		vis[u*177+v]=1; edge[u]+=v;
	}
	dp[1]=1;
	for (int i=1;i<n;i++) for (int j:edge[i]) dp[j]+=dp[i];
	cout<<dp[n]<<endl;	
}