Używając wyłącznie rezystorów o rezystancji $1\,[\Omega]$, skonstruuj rezystor o rezystancji $\sqrt{D}\,[\Omega]$.

Dana jest dodatnia liczba całkowita $D$. Skonstruuj spójny graf nieskierowany spełniający wszystkie poniższe warunki. W ramach ograniczeń tego zadania można udowodnić, że taki graf zawsze istnieje.

• Liczba wierzchołków $N$ mieści się w przedziale od $2$ do $300$ włącznie, a każdy wierzchołek ma unikalną etykietę od $1$ do $N$.
• Liczba krawędzi $M$ wynosi co najwyżej $300$, przy czym dozwolone są pętle własne oraz krawędzie wielokrotne.
• „Rezystancja zastępcza między wierzchołkiem $1$ a wierzchołkiem $N$”, zdefiniowana poniżej, mieści się w granicach błędu bezwzględnego $\pm 10^{-6}$ od $\sqrt{D}$.

Niech $G$ będzie spójnym grafem nieskierowanym o $n$ wierzchołkach i $m$ krawędziach ($n \ge 2$), i załóżmy, że $j$-ta krawędź łączy wierzchołki $a_j, b_j$. Rozważmy przypisanie liczby rzeczywistej $V_i$ ($i = 1, 2, \dots, n$) do każdego wierzchołka grafu $G$ oraz liczby rzeczywistej $I_j$ ($j = 1, 2, \dots, m$) do każdej krawędzi, tak aby spełnione były wszystkie poniższe równania:

• $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$

Można udowodnić, że takie przypisanie zawsze istnieje, a ponadto wartość $V_1 - V_n$ jest jednoznacznie określona. Wartość tę definiujemy jako „rezystancję zastępczą między wierzchołkiem $1$ a wierzchołkiem $n$”.

Wejście

Wejście składa się z pojedynczej dodatniej liczby całkowitej $D$ ($1 \le D \le 5000$).

Wyjście

W pierwszej linii wypisz liczbę wierzchołków $N$ oraz liczbę krawędzi $M$ skonstruowanego grafu, w tej kolejności, oddzielone spacjami.

W każdej z kolejnych $M$ linii, $i$-ta linia ($i = 1, 2, \dots, M$) powinna zawierać końce $i$-tej wybranej krawędzi, oddzielone spacją.

Jeśli istnieje wiele grafów spełniających warunki, można wypisać dowolny z nich.

Przykład

Wejście 1

1

Wyjście 1

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

Uwagi

Poniższa ilustracja przedstawia wyjście dla pierwszego przykładu.

Poniższa ilustracja przedstawia wyjście dla pierwszego przykładu.

To, że rezystancja zastępcza między wierzchołkiem $1$ a wierzchołkiem $n$ wynosi $1\,[\Omega]$, można wyjaśnić w następujący sposób:

• Ponieważ wszystkie rezystory mają rezystancję $1\,[\Omega]$, z symetrii wynika, że potencjały w wierzchołkach $2$ i $3$ są równe, więc rezystor między nimi można traktować tak, jakby nie istniał.
• W rezultacie obwód redukuje się do dwóch gałęzi połączonych równolegle, z których każda składa się z dwóch rezystorów $1\,[\Omega]$ połączonych szeregowo.
• Rezystancja zastępcza dwóch rezystorów $1\,[\Omega]$ połączonych szeregowo wynosi $2\,[\Omega]$, a rezystancja zastępcza dwóch rezystorów $2\,[\Omega]$ połączonych równolegle wynosi $1\,[\Omega]$.

Poniższe wyjście jest również uznawane za poprawne:

Wyjście 2

2 1
1 2