Description

Translated from COCI 2019/2020 Contest #6 T3. Konstrukcija

Let $G$ be a directed acyclic graph. If distinct vertices $c_1,c_2,c_3,\ldots c_n$ in $G$ satisfy that there is a path from $c_1$ to $c_2$, a path from $c_2$ to $c_3$, ..., and a path from $c_{n-1}$ to $c_n$, then the array $C = (c_1,c_2,c_3,\ldots c_n)$ is called an ordered array that starts at $c_1$ and ends at $c_n$.
Note that for any two adjacent elements $c_i,c_{i+1}$ in $C$, there does not have to be a direct edge between them; having a path is enough.

We also define the length of an ordered array $C = (c_1,c_2,c_3,\ldots c_n)$ as $\mathrm{len}(C) = n$. Therefore, the length of an ordered array is exactly the number of vertices it contains.
Note that an ordered array of length $1$ that starts and ends at the same vertex can exist.

Moreover, we define the sign of an ordered array $C = (c_1,c_2,c_3,\ldots c_n)$ as $\mathrm{sgn}(C) = (-1)^{\mathrm{len}(C)+1}$.
For vertices $x,y$ in $G$, let $S_{x,y}$ denote the set of all ordered arrays that start at $x$ and end at $y$.

Finally, we define the contradiction value between vertices $x,y$ as $\mathrm{tns}(x,y) = \sum\limits_{C \in S_{x,y}} \mathrm{sgn}(C)$.
That is, the contradiction value between $x$ and $y$ equals the sum of the signs of all ordered arrays that start at $x$ and end at $y$.

Given an integer $K$, you need to construct a directed acyclic graph with at most $1000$ vertices and $1000$ edges such that $\mathrm{tns}(1,N) = K$, where $N$ is the number of vertices.
Vertices are numbered by positive integers $1 \ldots N$.

Input Format

The first line contains one integer $K$。

Output Format

The first line contains two integers $N,M$, the number of vertices and edges in the directed acyclic graph you construct.
In the next $M$ lines, the $i$-th line contains two distinct integers $X_i,Y_i$, meaning the $i$-th edge is directed from $X_i$ to $Y_i$. Each edge should appear at most once.
Also, your construction must satisfy that for any two vertices, the absolute value of their contradiction value is at most $2^{80}$.
If there are multiple solutions, output any one of them.

0

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

1

1 0

2

6 8
1 2
1 3
1 4
1 5
5 4
2 6
3 6
4 6

Hint

Explanation for Sample 1

The constructed graph has $6$ vertices. The ordered arrays that start at $1$ and end at $6$ are:

• $(1, 6)$；
• $(1, 4, 6)$；
• $(1, 5, 6)$；
• $(1, 3, 6)$；
• $(1, 2, 6)$；
• $(1, 4, 3, 6)$；
• $(1, 4, 2, 6)$；
• $(1, 5, 3, 6)$；
• $(1, 5, 2, 6)$；
• $(1, 3, 2, 6)$；
• $(1, 4, 3, 2, 6)$；
• $(1, 5, 3, 2, 6)$。

Their lengths are $1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4$, respectively,
so their signs are $-1, 1, 1, 1, 1,-1,-1,-1,-1,-1, 1, 1$, respectively.
Therefore, the contradiction value between $1$ and $6$ is $-1 + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 - 1 + 1 + 1 = 0$。

Constraints

For $100\%$ of the testdata, $|K| \le 10^{18}$.
The limits for each subtask are shown in the table below:

Translated by ChatGPT 5