Problem Statement

This problem is based on Problem G. Please read Problem G first.

The following solution is one of the incorrect solutions to Problem G.

1. Repeat the following operations i and ii $\min(N,1000)$ times.
i. Among the vertices that have never been selected, select one vertex with the maximum degree. (If there are multiple vertices with the maximum degree, select one of them uniformly at random.)
ii. Compute "the number of vertices that are eventually painted black, assuming that the first player (eoeo) paints the vertex selected in i black."
2. Output the minimum of the values obtained in the computation of step 1.

nu50218 wants a test case that makes this solution fail. Create one test case with at least $1001$ and at most $2\times10^5$ vertices such that "the above solution outputs a wrong answer with probability at least 90%", and output it in the same format as the input of Problem G.

Input

No input is given in this problem.

Output

Create one test case satisfying the following constraints, and output it in the same format as the input of Problem G.

• $1001 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N \ (1 \leq i \leq N-1)$
• The graph is a tree.

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

Note If the output format is incorrect, it may not be judged correctly. The following programs (which are not correct as solutions) output in the correct format. Use them as a reference.

C++

#include <iostream>
using namespace std;

int main() {
    int N = 200000;

    cout << N << "\n";
    for (int i = 1; i < N; i++) {
        cout << i << " " << i + 1 << "\n";
    }

    return 0;
}

Python

N = 200000

print(N)
for i in range(1, N):
    print(i, i + 1)