Unique Tree Construction with Mismatched Centroid and Diameter Center

Given a positive integer n, construct a tree with n vertices (numbered 1 through n) such that all of the following hold:

• The tree has a unique diameter (i.e. there is exactly one longest simple path in the tree). The diameter of a tree is defined as the longest distance between any two vertices. For details see \(\text{diam}(T)\) in \(\LaTeX\) (e.g. \(\mathrm{diam}(T)=\max_{u,v}\,d(u,v)\)).
• The tree has a unique centroid (a vertex whose removal minimizes the size of the largest remaining connected component). For a tree \(T\) the centroid is defined in many texts (see e.g. [Tree Centroid](https://oi-wiki.org/graph/tree-centroid/) in \(\LaTeX\)).
• If we define the diameter's center as the center of the unique diameter (i.e. if the longest path is regarded as a tree then its center, which is unique if the path has an odd number of vertices), then this center must also be unique.
• Moreover, the centroid must not coincide with the diameter's center.

In other words, you must construct a tree \(T\) on n vertices satisfying

[ \begin{array}{l} {\rm (i)};\text{The diameter of }T \text{ is unique};\[6pt] {\rm (ii)};T \text{ has a unique centroid};\[6pt] {\rm (iii)};\text{The center (in the sense of graph‐center) of the diameter path is unique};\[6pt] {\rm (iv)};\text{The centroid is different from the diameter's center.} \end{array} ]

Note:

• The diameter of a tree is the longest path (see Tree Diameter).
• The centroid of a tree is defined in Tree Centroid.
• The diameter's center is defined by regarding the unique longest path as a tree and taking its center (which is unique if the path has an odd number of vertices).

It is guaranteed that if a solution exists then one can construct one in \(O(n)\) time. In this problem you may assume that \(n\) is such that a solution exists (for example, all test cases satisfy \(n \ge 7\); note that many known constructions require \(n\) to be odd, so for even \(n\) a valid answer always exists under the given guarantees).

inputFormat

The input consists of a single line containing one integer: n (the number of vertices).

\(1 \le n \le 10^5\)

outputFormat

Output exactly n-1 lines. Each line should contain two space‐separated integers u and v (1 ≤ u,v ≤ n) representing an edge of the tree. The tree must satisfy all the conditions described above.

sample

7

1 2
2 3
3 4
4 5
2 6
2 7