题目描述
Problem Description
E869120, the mayor of Paken City, plans to build several checkpoints and some one-way roads connecting pairs of checkpoints in the city.
Let the number of checkpoints be $ N $, and number the checkpoints as $ 1, 2, 3, ..., N $.
From ancient times, the lucky number of this city has been $ K $.
Therefore, the mayor decided to build the checkpoints and roads satisfying the following conditions:
- The number of ways to go from checkpoint $ 1 $ to checkpoint $ N $ is exactly $ K $.
- Among the ways to go from checkpoint $ 1 $ to checkpoint $ N $, any path chosen will pass through the same number of roads.
For example, when $ K = 5 $, the following configuration of checkpoints and roads satisfies the conditions. This is because the total number of ways to go from checkpoint $ 1 $ to checkpoint $ N $ is $ K = 5 $, and all ways pass through exactly $ 3 $ roads.
Due to cost considerations, the mayor wants to minimize the number of checkpoints $ N $ as much as possible.
Construct one such way of building the checkpoints and roads. However, a road directly connecting checkpoint $ a $ to checkpoint $ b $ can only be built if $ a < b $, and multiple "roads connecting the same pair of checkpoints" cannot be built.
Input Format
The input is given from the standard input in the following format:
$ K $
Output Format
Output should be in the following format:
$ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ a_3 $ $ b_3 $ ... $ a_M $ $ b_M $
- On the first line, output the number of checkpoints $ N $ and the number of roads $ M $ separated by a space.
- For the next $ M $ lines, output the road information. Here, $ a_i, b_i $ represent that the $ i $-th road directly connects checkpoint $ a_i $ to checkpoint $ b_i $. It must be ensured that $ a_i < b_i $.
- End with a newline. However, $ N $ must be $ 200 $ or less. Otherwise, it will result in Wrong Answer.
Also, $(a_i, b_i) \neq (a_j, b_j) (i \neq j)$ and $ a_i < b_i $ must be satisfied.
Sample Input and Output
Sample Input #1
5
Sample Output #1
7 10
1 2
1 3
1 4
2 5
3 5
3 6
4 5
4 6
5 7
6 7
Sample Input #2
20
Sample Output #2
16 24
1 2
2 3
3 4
5 6
6 7
7 8
9 10
10 11
11 12
13 14
14 15
15 16
1 5
5 9
9 13
2 6
6 10
10 14
3 7
7 11
11 15
4 8
8 12
12 16
Sample Input #3
104
Sample Output #3
21 75
1 2
1 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 21
9 21
10 21
11 21
12 21
13 21
14 21
15 21
16 21
17 21
18 21
19 21
20 21
Notes/Hints
Constraints
- $ K $ is an integer between $ 1 $ and $ 10^{18} $ inclusive.
Subtasks
Subtask $ 1 $ \[$ 8 $ points\]
- $K \leq 150$
Subtask $ 2 $ \[$ 12 $ points\]
- $K \leq 8000$
Subtask $ 3 $ \[$ 80 $ points\]
- No additional constraints.
For Subtask $ 3 $, scoring will be done as follows, where $ L $ is the maximum value of $ N $ across all test cases:
- If $161 \leq L \leq 200$, $ 15 $ points
- If $152 \leq L \leq 160$, $ 55 - (L - 150) * 2 $ points
- If $ L = 151 $, $ 65 $ points
- If $L \leq 150$, full $ 80 $ points
Sample Explanation 1
In the following diagram, there are $ 5 $ ways to go from checkpoint $ 1 $ to checkpoint $ 7 $, and all ways pass through the same number ($ 3 $) of roads, satisfying the conditions. 
Sample Explanation 2
In the following diagram, there are $ 20 $ ways to go from checkpoint $ 1 $ to checkpoint $ 16 $, and all ways pass through the same number ($ 6 $) of roads, satisfying the conditions. 
Sample Explanation 3
This input satisfies the constraints of Subtask $ 1 $.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分