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
#include <iostream>
#include <set>
#include <list>

int main() {

    int graph[100][2];
    for (auto &i : graph) {
        i[0] = i[1] = -1;
    }

    int lastVertex = 0;
    long long k;
    std::cin >> k;
    if (k == 1) {
        graph[0][0] = 1;
        lastVertex = 1;
    } else {
        auto sizesToCreate = std::set<int>();
        auto vertexesToConnectLast = std::list<int>();
        long long POW[32];
        for (int i = 0; i < 32; i++) {
            POW[i] = (long long) 0x1 << i;
        }
        for (int i = 31; i >= 0; i--) {
            if (k >= POW[i]) {
                sizesToCreate.emplace(i);
                k -= POW[i];
            }
        }

        int used = 0;
        auto it = sizesToCreate.begin();
        while (it != sizesToCreate.end()) {
            int i = *it;
            while (i - used > 0) {
                int a = lastVertex++;
                int b = lastVertex++;
                int c = lastVertex;
                graph[a][0] = b;
                graph[a][1] = c;
                graph[b][0] = c;
                used++;
            }
            it = sizesToCreate.erase(it);
            if (!sizesToCreate.empty()) {
                vertexesToConnectLast.push_back(lastVertex);
                int next = lastVertex + 1;
                graph[lastVertex][0] = next;
                lastVertex = next;
            }
        }

        for (auto i: vertexesToConnectLast) {
            graph[i][1] = lastVertex;
        }

    }
    std::cout << lastVertex + 1 << std::endl;
    for (int i = 0; i <= lastVertex; i++) {
        std::cout << (graph[i][0] > 0 ? graph[i][0] + 1 : -1) << " " << (graph[i][1] > 0 ? graph[i][1] + 1 : -1)
                  << std::endl;
    }
    return 0;
}