Trees and Path Lengths 2

You are given an integer $S$. Build a tree that has exactly $S$ simple paths of length 3. The number of vertices $N$ must be at least 1 and at most 500.

A simple path never visits the same vertex twice, and its length is the number of edges on it. Direction does not matter, so A-B-C-D and D-C-B-A are the same path.

Many trees satisfy the condition, so the shape of the tree you print is restricted as follows and the answer becomes unique.

The vertices are numbered 0 to $N-1$. Start from the path formed by the edges (0, 1), (1, 2), (2, 3), then attach leaves to it. Only vertices 0, 1 and 3 can receive leaves, and they receive $p$, $q$ and $r$ leaves respectively ($p, q, r \ge 0$). The new leaves are numbered from 4 upward: first the leaves of vertex 0, then the leaves of vertex 1, then the leaves of vertex 3. So $N = 4 + p + q + r$.

Among the trees of this shape that have exactly $S$ simple paths of length 3, print the one with the smallest $N$. If several trees share that smallest $N$, print the one whose triple $(p, q, r)$ is lexicographically smallest. Such a tree exists for every $S$ in the given range, and its $N$ is always at most 500.

The first line contains $S$. ($1 \le S \le 10000$)

Print the number of vertices $N$ on the first line.

On each of the next $N-1$ lines, print the two endpoints of one edge, separated by a space. Print the edges (0, 1), (1, 2), (2, 3) first, in that order, then the leaf edges in increasing order of leaf number. In a leaf edge, write the number of the vertex the leaf is attached to first and the number of the leaf second.