En utilisant uniquement des résistances de 1 [Ω], construisez une résistance de $\sqrt{D}$ [Ω].

Vous recevez un entier positif $D$. Construisez un graphe non orienté connexe satisfaisant toutes les conditions suivantes. Sous les contraintes de ce problème, il peut être prouvé qu'un tel graphe existe toujours.

• Le nombre de sommets $N$ est compris entre 2 et 300 inclus, et chaque sommet possède une étiquette distincte de 1 à $N$.
• Le nombre d'arêtes $M$ est au plus 300, et les boucles ainsi que les arêtes multiples sont autorisées.
• La « résistance effective du sommet 1 au sommet $N$ », définie ci-dessous, est à une erreur absolue de $\pm 10^{-6}$ près de $\sqrt{D}$.

Soit $G$ un graphe non orienté connexe avec $n$ sommets et $m$ arêtes ($n \geq 2$), et supposons que la $j$-ième arête relie les sommets $a_j, b_j$. Considérons l'assignation d'un nombre réel $V_i$ ($i = 1, 2, \dots, n$) à chaque sommet du graphe $G$, et d'un nombre réel $I_j$ ($j = 1, 2, \dots, m$) à chaque arête, de sorte que toutes les équations suivantes soient satisfaites :

• $I_j = V_{a_j} - V_{b_j}$ ($j = 1, 2, \dots, m$)
• $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0$ ($i = 2, 3, \dots, n - 1$)
• $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

Il peut être prouvé qu'une telle assignation existe toujours, et de plus, que la valeur de $V_1 - V_n$ est déterminée de manière unique. Nous définissons cette valeur comme la « résistance effective du sommet 1 au sommet $n$ ».

Entrée

L'entrée consiste en un seul entier positif $D$ ($1 \leq D \leq 5000$).

Sortie

Sur la première ligne, imprimez le nombre de sommets $N$ et le nombre d'arêtes $M$ du graphe construit, dans cet ordre, séparés par des espaces.

Sur chacune des $M$ lignes suivantes, la $i$-ième ligne ($i = 1, 2, \dots, M$) doit contenir les extrémités de la $i$-ième arête choisie, séparées par un espace.

S'il existe plusieurs graphes satisfaisant les conditions, n'importe lequel d'entre eux peut être imprimé.

Exemples

Entrée 1

1

Sortie 1

4 5
1 2
1 3
2 3
2 4
3 4

Remarque

L'illustration suivante représente la sortie pour le premier exemple.

Le fait que la résistance effective du sommet 1 au sommet $n$ soit 1 [Ω] peut être expliqué comme suit :

• Puisque toutes les résistances ont une résistance de 1 [Ω], et par symétrie, les potentiels aux sommets 2 et 3 sont égaux, la résistance entre eux peut être traitée comme si elle n'existait pas.
• En conséquence, le circuit se réduit à deux branches en parallèle, chaque branche étant constituée de deux résistances de 1 [Ω] en série.
• La résistance effective de deux résistances de 1 [Ω] en série est de 2 [Ω], et la résistance effective de deux résistances de 2 [Ω] en parallèle est de 1 [Ω].

La sortie suivante est également considérée comme correcte :

2 1
1 2