Стійке дерево
Limits: 2 sec., 512 MiB
Для дерева \(T\) визначимо функцію \(f_T(d)\), яка ставить у відповідність цілому числу \(d\) кількість вершин дерева \(T\) із степенем \(d\). Степінь вершини — це кількість сусідніх вершин до неї.
Стійкістю дерева \(T\) називається мінімальне значення \(f_T(\deg(v))\) серед усіх вершин \(v\) дерева \(T\). \(\deg(v)\) позначає степінь вершини \(v\).
Задано натуральне число \(n\).
Побудуйте дерево з \(n\) вершин з найбільшою стійкістю. Зауважте, що вершини дерева нумеруються з 1.
Input
В одному рядку задано натуральне число \(n\).
Output
У першому рядку виведіть ціле число — найбільшу стійкість дерева.
У наступних \(n - 1\) рядках виведіть по два цілих числа \(u\), \(v\) — номери вершин, з’єднаних ребром у дереві.
Якщо відповідей декілька, виведіть будь-яку.
Constraints
\(2 \le n \le 10^5\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 2 | 2 1 2 |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 | 2 1 2 2 3 3 4 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|