Problem Description

This problem is translated from PA 2020 Round 5 Skierowany graf acykliczny.

As the name suggests, a Directed Acyclic Graph (Directed Acyclic Graph, DAG for short) is a directed graph without cycles.

If we choose two nodes in such a graph, we can compute how many different directed paths exist between these nodes. If one path contains an edge and another path does not contain this edge, then we consider these two paths different.

Your task is to construct a directed acyclic graph with $n$ nodes (numbered from $1$ to $n$) such that there are exactly $k$ paths from node $1$ to node $n$. Your graph can have at most $100$ nodes, each node can have at most two outgoing edges, and it cannot contain multiple edges (that is, if a node has two outgoing edges, they must go to different nodes). It can be proven that for every $k$ satisfying the constraints in the input, a valid graph can be constructed.

Input Format

One line with one integer $k$.

Output Format

The first line prints one integer $n$, which is the number of nodes in the graph you construct.

Then output $n$ lines, each with two integers. The $i$-th line describes the destination node numbers of the outgoing edges starting from node $i$. Either of these two numbers can be $-1$, meaning that this edge does not exist. If both numbers are not $-1$, then they must not be equal.

If there are many valid graphs, you may output any of them. Note that you do not need to minimize the number of nodes, and under the limits the number of nodes is sufficient.

3

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

Hint

Sample 1 Explanation

The figure below shows a directed acyclic graph with $6$ nodes from the output. There are three paths from $1$ to $6$: $1\to 3\to 2\to 6$, $1\to 3\to 6$, and $1\to 5\to 6$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1\le k\le 10^9$ and $2\le n\le 100$.

Translated by ChatGPT 5