Стійке дерево

Обмеження: 2 сек., 512 МіБ

Для дерева \(T\) визначимо функцію \(f_T(d)\), яка ставить у відповідність цілому числу \(d\) кількість вершин дерева \(T\) із степенем \(d\). Степінь вершини — це кількість сусідніх вершин до неї.

Стійкістю дерева \(T\) називається мінімальне значення \(f_T(\deg(v))\) серед усіх вершин \(v\) дерева \(T\). \(\deg(v)\) позначає степінь вершини \(v\).

Задано натуральне число \(n\).

Побудуйте дерево з \(n\) вершин з найбільшою стійкістю. Зауважте, що вершини дерева нумеруються з 1.

Вхідні дані

В одному рядку задано натуральне число \(n\).

Вихідні дані

У першому рядку виведіть ціле число — найбільшу стійкість дерева.

У наступних \(n - 1\) рядках виведіть по два цілих числа \(u\), \(v\) — номери вершин, з’єднаних ребром у дереві.

Якщо відповідей декілька, виведіть будь-яку.

Обмеження

\(2 \le n \le 10^5\).

Приклади