Constructing a Minimal Tree with Prescribed Grundy Number

Kuon loves trees – but she prefers them to be as small as possible. She will label every node of a tree with a positive integer such that any two adjacent nodes have different labels. Among all valid labelings the one with the minimum total sum of labels is chosen. It can be proven that when a tree is optimally labeled in this way, the label on each node equals the minimum excludant (mex) of the set of labels of its (already‐labeled) neighbors. In other words, if a node’s neighbors have been assigned the set S of positive integers, then its optimal label is:

Because every tree is bipartite one might expect that only the numbers 1 and 2 are ever used. However, by cleverly choosing the tree structure and the order in which its nodes are "forced" (via connectivity) to use labels, one may force a node to have a label as high as k for any given positive integer k. In fact, one may show that the minimum number of nodes needed to force a node to get label k is 2^(k-1).

This task asks you: Given an integer k as input, construct a tree (i.e. an undirected connected acyclic graph) that has at most 2^(k-1) nodes and that, when optimally labeled by Kuon, has at least one node with a label of k (or higher). One valid construction is the following recursive tree T(k):

• T(1) is a single node (its optimal label is 1).
• For k > 1, define T(k) to be a new tree whose root is connected to the roots of trees T(1), T(2), …, T(k-1). In this construction, the root’s set of neighbor labels becomes {1, 2, …, k-1} and so its optimal label is k.

Your program is to output T(k) in the following format: The first line contains an integer n – the number of nodes in the tree. The next n-1 lines each contain two integers u v (1 ≤ u, v ≤ n) indicating an edge between nodes u and v. The nodes are numbered arbitrarily. If there are multiple valid answers, you may output any one of them.

inputFormat

The input consists of a single integer k (1 ≤ k ≤ 10), which is the target minimum maximum label after the optimal labeling.

outputFormat

Output a valid tree in the following format:

1. The first line contains an integer n, the number of nodes in the tree.
2. The following n-1 lines each contain two integers u and v representing an edge of the tree.

The tree must be such that when it is optimally labeled (each node gets the mex of the set of labels of its neighbors that are already labeled) one of the nodes (specifically, the root in the recursive construction) will receive a label of at least k.

sample

1

1