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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <random>
#include <cmath>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <climits>
#include <stack>
#include <random>
#include <bitset>
#include <numeric>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define trav(a, x) for(auto& a : x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;

#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

int k;

void verify(const vector<pii>& edges) {
	return ;
	int n = sz(edges);
	vi f(n + 1);
	f[n] = 1;
	auto vert = [&](int pson) {
		if (pson == -1) return -1;
		return n - pson;
	};
	auto val = [&](int son) {
		if (son == -1) return 0;
		return f[vert(son)];
	};
	rep(idx, 1, n) {
		printf("node: %d, has edges: %d, %d\n", vert(idx), vert(edges[idx].st), vert(edges[idx].nd));
		f[vert(idx)] = val(edges[idx].st) + val(edges[idx].nd);
	}
	rep(i, 1, n+1) {
		printf("f[%d] = %d\n", i, f[i]);
	}
	assert(f[1] == k);
}

void printGraph(const vi& verts, const vector<pii>& edges) {
	printf("%d\n", sz(verts));
	int n = sz(verts);
	auto vert = [&](int x) {
		if (x == -1) return -1;
		return n - x;
	};
	ford(i, sz(edges), 0) {
		printf("%d %d\n", vert(edges[i].st), vert(edges[i].nd));
	}
	verify(edges);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	scanf("%d", &k);
	vi verts, ways;
	vector<pii> edges;

	auto noWays = [&](int vert) {
		return vert != -1 ? ways[vert] : 0;
	};
	auto addVert = [&](int lson = -1, int rson = -1) {
		int v = sz(verts);
		verts.pb(v);
		ways.pb(noWays(lson) + noWays(rson));
		edges.pb({lson, rson});
		return v;
	};

	verts.pb(0);
	ways.pb(1);
	edges.pb({-1, -1});

	addVert(0);

	while (ways.back() + ways[sz(ways) - 2] <= k) {
		addVert(verts.back(), verts[sz(verts) - 2]);
	}
	int nk = k;
	vi mojRozklad;
	ford(idx, sz(ways), 0) {
		if (nk >= ways[idx]) {
			mojRozklad.pb(verts[idx]);
			nk -= ways[idx];
		}
	}
	// printf("moj rozklad: "); trav(x, mojRozklad) printf("%d ", x); printf("\n");

	if (sz(mojRozklad) == 1) {
		printGraph(verts, edges);
		return 0;
	}
	int lastVert = addVert(mojRozklad.back(), mojRozklad[sz(mojRozklad) - 2]);
	for (int wsk = sz(mojRozklad) - 3; wsk >= 0; --wsk) {
		lastVert = addVert(lastVert, mojRozklad[wsk]);
	}
	printGraph(verts, edges);
}