Description
Using only resistors with resistance $1\,[\Omega]$, construct a resistor with resistance $\sqrt{D}\,[\Omega]$.
You are given a positive integer $D$. Construct one connected undirected graph satisfying all of the following conditions. Under the constraints of this problem, it can be proven that such a graph always exists.
- The number of vertices $N$ is between $2$ and $300$ ($2$ and $300$ inclusive), and each vertex has a distinct label from $1$ to $N$.
- The number of edges $M$ is at most $300$, and self-loops and multiple edges are allowed.
- The "effective resistance from vertex $1$ to vertex $N$", defined as below, is within an absolute error of $\pm 10^{-6}$ from $\sqrt{D}$.
Let $G$ be a connected undirected graph with $n$ vertices and $m$ edges ($n \ge 2$), and suppose that the $j$-th edge connects vertices $a_j, b_j$. Consider assigning a real number $V_i$ ($i = 1, 2, \dots, n$) to each vertex of graph $G$, and a real number $I_j$ ($j = 1, 2, \dots, m$) to each edge, so that all of the following equations are satisfied:
- $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$
It can be proven that such an assignment always exists, and furthermore that the value of $V_1 - V_n$ is uniquely determined. We define this value as the "effective resistance from vertex $1$ to vertex $n$".
Input
The input consists of a single positive integer $D$. ($1 \le D \le 5000$)
Output
On the first line, print the number of vertices $N$ and the number of edges $M$ of the constructed graph, in this order, separated by spaces.
On each of the following $M$ lines, the $i$-th line ($i = 1, 2, \dots, M$) should contain the two endpoints of the $i$-th edge, separated by a space.
If there are multiple graphs satisfying the conditions, any one of them may be printed.
Examples
Input 1
1
Output 1
4 5 1 2 1 3 2 3 2 4 3 4
Note
The following is an illustration of the output for Example 1.
That the effective resistance from vertex $1$ to vertex $n$ is $1\,[\Omega]$ can be explained as follows:
- Since all resistors have resistance $1\,[\Omega]$, and by symmetry the potentials at vertices $2$ and $3$ are equal, the resistor between them can be treated as if it does not exist.
- As a result, the circuit reduces to two branches in parallel, each branch consisting of two $1\,[\Omega]$ resistors in series.
- The effective resistance of two $1\,[\Omega]$ resistors in series is $2\,[\Omega]$, and the effective resistance of two $2\,[\Omega]$ resistors in parallel is $1\,[\Omega]$.
The following output is also considered correct:
2 1 1 2