Опис
Використовуючи лише резистори з опором $1\,[\Omega]$, сконструюйте резистор з опором $\sqrt{D}\,[\Omega]$.
Задано додатне ціле число $D$. Побудуйте один зв'язний неорієнтований граф, який задовольняє всі наведені нижче умови. За обмежень цієї задачі можна довести, що такий граф завжди існує.
- Кількість вершин $N$ лежить у межах від $2$ до $300$ (включно з $2$ та $300$), і кожна вершина має унікальний номер від $1$ до $N$.
- Кількість ребер $M$ не перевищує $300$, дозволяються петлі та кратні ребра.
- «Еквівалентний опір між вершиною $1$ і вершиною $N$», визначений нижче, відрізняється від $\sqrt{D}$ за абсолютною похибкою не більше ніж на $\pm 10^{-6}$.
Нехай $G$ — зв'язний неорієнтований граф із $n$ вершинами та $m$ ребрами ($n \ge 2$), і нехай $j$-те ребро з'єднує вершини $a_j, b_j$. Розглянемо зіставлення кожній вершині графа $G$ дійсного числа $V_i$ ($i = 1, 2, \dots, n$), а кожному ребру — дійсного числа $I_j$ ($j = 1, 2, \dots, m$) так, щоб виконувалися всі такі рівняння:
- $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
- $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
- $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$
Можна довести, що таке зіставлення завжди існує, і ба більше, значення $V_1 - V_n$ визначається однозначно. Ми визначаємо це значення як «еквівалентний опір між вершиною $1$ і вершиною $n$».
Вхідні дані
Вхідні дані складаються з одного додатного цілого числа $D$. ($1 \le D \le 5000$)
Вихідні дані
У першому рядку виведіть кількість вершин $N$ і кількість ребер $M$ побудованого графа в цьому порядку через пробіл.
У кожному з наступних $M$ рядків $i$-й рядок ($i = 1, 2, \dots, M$) має містити два кінці $i$-го ребра через пробіл.
Якщо існує декілька графів, що задовольняють умови, дозволяється вивести будь-який із них.
Приклади
Вхідні дані 1
1
Вихідні дані 1
4 5 1 2 1 3 2 3 2 4 3 4
Примітка
Нижче наведено ілюстрацію вихідних даних для Прикладу 1.
Те, що еквівалентний опір між вершиною $1$ і вершиною $n$ дорівнює $1\,[\Omega]$, можна пояснити так:
- Оскільки всі резистори мають опір $1\,[\Omega]$, а через симетрію потенціали у вершинах $2$ і $3$ рівні, резистор між ними можна вважати відсутнім.
- У результаті коло спрощується до двох паралельних гілок, кожна з яких складається з двох послідовно з'єднаних резисторів по $1\,[\Omega]$.
- Еквівалентний опір двох послідовно з'єднаних резисторів по $1\,[\Omega]$ дорівнює $2\,[\Omega]$, а еквівалентний опір двох паралельно з'єднаних резисторів по $2\,[\Omega]$ дорівнює $1\,[\Omega]$.
Наведені нижче вихідні дані також вважаються правильними:
2 1 1 2