問題文

この問題は G 問題 がテーマです。先に G 問題 を読んでください。

以下の解法は、 G 問題における誤解法の一つです。

1. 以下の i と ii の操作を $\min(N,1000)$ 回繰り返す。
i. 一度も選択されていない頂点のうち、次数が最大の頂点を一つ選択する。(次数が最大であるような頂点が複数存在するなら、そのうち一つを一様ランダムに選択する)
ii. 「 i で選択された頂点を先手 (eoeo) が黒く塗ると仮定したとき、最終的に黒く塗られる頂点数」を計算する。
2. 1 の計算で得た値の最小値を出力する。

nu50218 はこの解法を落とすテストケースが欲しいです。 頂点数が $1001$ 以上 $2\times10^5$ 以下の「上記の解法が 90% 以上の確率で間違った答えを出力するテストケース」を一つ作成し、G 問題の入力と同じ形式で出力してください。

入力

この問題では入力は与えられません。

出力

以下の制約を満たすテストケースを一つ作成し、G 問題の入力と同じ形式で出力してください。

• $1001 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N \ (1 \leq i \leq N-1)$
• 木である

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

注意 出力のフォーマットが正しくない場合、正しく判定されない可能性があります。 以下のプログラムは（解法としては正しくないですが）正しいフォーマットで出力します。参考にしてください。

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)