△

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, build a tree on N vertices that minimizes the sum of distances over all vertex pairs, then print that minimum and the edges.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Given a tree with $N$ vertices, build a tree that minimizes the sum of distances between all pairs of vertices. The vertices are numbered from $1$ to $N$ .

That is, the tree should minimize $\sum_{1 \leq i < j \leq N} \textrm{dist}(i, j)$ , where $\textrm{dist}(i, j)$ is the distance between vertices $i$ and $j$ .

Input

The first line contains the number of vertices $N$ . ( $2 \leq N \leq 100\,000$ )

Output

On the first line, print the minimum possible sum of distances between all pairs of vertices.

From the second line, print $N-1$ lines describing the edges of the tree. Each line contains the two vertex numbers connected by an edge, separated by a space. If several trees satisfy the condition, print any one of them.

Examples1

Example 1
Input
```
3
```
Expected output
```
4
2 1
1 3
```