1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
 *  Copyright (C) 2020  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include <cmath>
#include <iostream>
#include <vector>
#include <list>
#include <bitset>
using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int k;
	cin >> k;

	// special case
	if (k == 1) {
		cout << "2" << endl << "2 -1" << endl << "-1 -1" << endl;
		return 0;
	}

	bitset<32> bits(k);
	int extra = max(2, (int)bits.count() - 1);
	int n = 2 * (int)log2(k) + extra - 1;
	int prime_node = extra + 1;

	vector<list<int>> graph(n);

	// connect all nodes in a straight line
	for (int i = 0; i < n; ++i) {
		graph[i].emplace_back(i + 1);
	}

	/* Add alternative paths in two halves (top and bottom):
	 * - bottom half encodes the highest bit - 2 ** log2(k)
	 * - top reuses bottom edges to encode the 2 ** e - 1 states
	 *   (it requires one extra node per edge)
	 *
	 *               /^^^^^^^^^^^^^^\     = 1
	 *          /^^^/^^^^^^^^^\      \    = 2
	 *      /^^/^^^/^^^\       \      \   = 4
	 * O---O---O---O---X---O---O---O---O  (X is prime node)
	 * \______________/\______/\_______/  = 8
	 */

	// bottom half - all edges connected
	for (int i = n; i > prime_node; i -= 2) {
		graph[i - 2].emplace_back(i);
	}
	graph[0].emplace_back(prime_node);

	// top half - edges represent the bits needed
	int index = 0;
	int size = (int)log2(k) - 1;
	for (int i = 0; i <= size; ++i) {
		if (bits[size - i]) {
			graph[++index].emplace_back(prime_node + 2*i);
		}
	}

	// print graph
	cout << n + 1 << endl;
	int i = 0;
	for (auto list: graph) {
		int edge = list.front() == list.back() ? -2 : list.back();
		cout << list.front() + 1 << " " << edge + 1 << endl;
	}
	cout << "-1 -1" << endl;
	return 0;
}