「PA 2020」Skierowany graf acykliczny

题目描述

正如名字所示，有向无环图（Directed Acyclic Graph，简称 DAG）是一个无环的有向图。

如果我们在这样一个图中选择两个节点，我们可以计算出这些节点之间存在多少条不同的有向路径。如果其中一条路径包含一条边而另一条不包含这条边，我们就认为这两条路径是不同的。

你的任务是构造一个 $n$ 个节点（编号从 $1$ 到 $n$）的有向无环图，其中从节点 $1$ 到节点 $n$ 正好有 $k$ 条路径。你的图最多可以有 $100$ 个节点，每个节点最多可以有两条出边，而且不能包含重边（即如果一个节点有两条出边，它们必须通向不同的节点）。可以证明，对于每一个满足输入中约束条件的 $k$，都可以构造一个满足条件的图。

输入格式

一行一个整数 $k$ ($1 \leq k \leq 10^9$)。

输出格式

第一行输出一个整数 $n$ ($2 \leq n \leq 100$)，表示你构造的图中节点的个数。

接下来 $n$ 行，每行两个整数。第 $i$ 行表示以编号为 $i$ 的节点为起点的出边到达的节点编号。这两个数中任何一个都可以是 $-1$，表示不存在这条边。如果两个数都不是 $-1$，那这两个数不应该相等。

如果有许多满足条件的图，你可以输出任何一个。注意你不需要最小化节点个数，且在限制之下图节点个数是足够的。

样例

输入

3

输出

6
3 5
6 -1
2 6
2 6
6 -1
-1 -1

下图展示了输出中 $6$ 个节点的有向无环图，从 $1$ 到 $6$ 有三条路径：$1 \to 3 \to 2 \to 6$, $1 \to 3 \to 6$ 和 $1 \to 5 \to 6$。