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>
struct wierzcholek{
    int l,r;
}v[111];
int k,licznik=0,last=0,allbits,bk,oldest=0;
char bit[200];
int tab[130];


void look(int p){
    if( p==last ){
        licznik++;
/*
        for(int i=0; i<last && tab[i]<last; i++)
            if(tab[i]>0)
                printf("%d ",tab[i]);
        printf("%d\n",last);
*/
        return;
    }

    if(v[p].l >0){
        //licznik++;
        tab[p] = v[p].l;
        look( v[p].l );
        tab[p] = -1;

    }
    if(v[p].r >0){
        //licznik++;
        tab[ p ] = v[p].r;
        look( v[p].r );
        tab[ p ] = -1;
    }

    return;
}

void showGraph(){

    //show output info
    printf("old:  %d\nbits: %d\n\n",oldest,allbits);
    for(int i=32; i>=0; i--){
        printf("%d",bit[i]);
    }
    printf("\n");

    //rysuj wierzcholki i zlicz unikalne drogi
    for(int i=1; i <= last ; i++){
        printf("%d: l: %02d r: %02d\n",i,v[i].l,v[i].r);
    }
    look(1);
    printf("\nOdnaleziono drog:%d\n",licznik);
}

int main(){
    //init
    for(int i=0; i<110; i++){
        v[i].l = -1;
        v[i].r = -1;
    }
    scanf("%d",&k);

    if(k==1){
        printf("2\n");
        printf("2 -1\n");
        printf("-1 -1\n");
        return 0;
    }
//switch to bytes
    for(int i=0, bk=k; i<=32 && bk>0; i++){
        bit[ i ] = bk % 2;
        if(bk%2 == 1){
            oldest = i;
            allbits++;
        }
        bk /= 2;
    }

// CREATING CATERPILLAR *<><><><>
//make head
    v[1].l = 2;

//make main body - oldest bit length
    for(int i=2; i<oldest*3+2; i+=3 ){
       v[i].l = i+1;
       v[i].r = i+2;

       v[i+1].l = i+3;
       v[i+2].l = i+3;
    }
//end of creature
    last = oldest * 3 +2;
    v[ last - 1 ].l += allbits - 1 - bit[0];
    v[ last - 2 ].l += allbits - 1 - bit[0];

//attach legs
    for(int i = oldest - 1, j=1; i>0; i--, j++ ){
        if(bit[j]==1){
            v[ j*3 ].r = last;
            if(i > 1)
                v[ last++ ].l = (j*3) + (i-1)*3 +2;
            else
                v[ last++ ].l = (j*3) + 2;

        }
    }

//attach stick
    if(bit[0]==1){
        v[ 1 ].r = last;
    }

    //showGraph();
    printf("%d\n",last);

    for(int i=1; i<=last; i++)
        printf("%d %d\n",v[ i ].l, v[ i ].r);

    return 0;
}