Background

Source: Eight Immortals Toasting, this can be clicked.

• Lü Dongbin — Drunkenly lifting a kettle, strength like a thousand jin;
• Tieguai Li — Spinning elbow and knee strike, drunk yet still real;
• Han Zhongli — Stumbling steps, hugging the jar, Douxin Top;
• Lan Caihe — One-hand toast, breaking at the waist;
• Zhang Guolao — Drunkenly tossing a cup, continuous kicking combo;
• Cao Guojiu — Immortal’s toast, throat-locking hook;
• Han Xiangzi — Grabbing the wrist and striking the chest, drunkenly playing the flute;
• He Xiangu — Bending the waist to offer wine, drunkenly swaying steps.

Problem Description

Given a positive integer $n$, you need to construct a tree with $n$ nodes such that the centroid of the tree’s diameter is not the centroid of the tree.

At the same time, this tree must satisfy: the diameter$^1$, the centroid$^2$, and the centroid of the diameter$^3$ are all unique.

Notes:

• Tree diameter$^1$: https://oi-wiki.org/graph/tree-diameter/
• Tree centroid$^2$: https://oi-wiki.org/graph/tree-centroid/
• Centroid of the diameter$^3$: treat the tree diameter (a chain) as a tree, and find its center (a single node).

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

Output Format

Output a positive integer $n$ on the first line.

Then output $n-1$ lines. Each line contains two positive integers $u, v$, representing an edge of the tree.

If there is no solution, output -1.

This problem uses a Special Judge. Any valid solution will be accepted.

20

20
20 18
1 3
19 12
19 4
16 1
4 1
1 7
16 10
7 20
13 8
10 2
18 13
13 17
14 18
11 19
16 5
2 6
16 9
17 15

2

-1

Hint

Sample Explanation

In Sample #1, the centroid of the diameter is $7$, and the centroid of the tree is $1$. Thus, $1 \ne 7$.

In Sample #2, $n = 2$. With only two nodes, the centroid is obviously impossible to be unique.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata: $1 \le n \le 10^4$.

The Special Judge source code is provided; see the attachment below.

Translated by ChatGPT 5