#include <iostream>
#define FIN "graph.in"
#define SIZE 50

using namespace std;

int mat[SIZE][SIZE], stack[SIZE],
nodes,
k,
start_node;

void loadGraph() {
    int i, j;
    //freopen(FIN, "r",stdin);
     //citim numarul de noduri
     cin>>nodes;

     //citim muchiile (i,j)
     //de la i la j si de la j la i
     while(cin>>i>>j) {
       mat[i][j] = 1;
       mat[j][i] = 1;
     }
}

void displayGraph() {

     for(int i = 1; i <= nodes; i++) {
        for(int j = 1; j <= nodes; ++j) {
          printf("%d ", mat[i][j]);
        }

        printf("\n");
     }
}

void init() {
    //k = 2; stack[2] = 0
    stack[ k ] = 0;
}

int succ() {

    if(stack[k] < nodes) {//0 < 9 ?

       stack[k]++;//stack[k] = 1 + 1 = 2 (varful) stack[k] = 2
       return 1;
    }
    return 0;
}

int valid() {

    if(!mat[ stack[k-1] ] [ stack[k] ]) return 0;

    for(int i = 1; i < k ; ++i)

           if(stack[i] == stack[k]) return 0;

    return 1;
}

int sol() {

    return (k == nodes) && (mat[ start_node ][ stack[k] ] == 1);
}

void display_solution() {

     for(int i = 1; i <= nodes; ++i) printf("%d ", stack[i]);

     printf("%d", start_node);
     printf("\n");
}

//backtracking iterative
void bkt() {

     int h, v;

     k = 2;

     init();

     while(k > 1) {

           h = 1;
           v = 0;
           while(h && !v) {
               h = succ();
               if(h) v = valid();
           }

           if(h) {

             if(sol()) {
                display_solution();
                //k = 1;
             } else {
               k++;init();
             }

           } else k--;
     }

}

int main(int argc, char const *argv[]) {

  printf("%s","Nodul de start = ");
  scanf("%d", &start_node);

  loadGraph();
  printf("%s\n", "Graful neorientat");
  displayGraph();

  stack[1] = start_node;
  //k = 2;
  //stack[2] = 1;

  printf("%s\n","Drumuri hamiltoniene:");
  bkt();

  return 0;
}

//k=3; stack[k] :3
//k=2; stack[k] :2
                //muchie
//k=1; stack[k] :1 (varf)

//stack[k] = Varf

//node_start = 5

//stack[1] = 5

             //init()
//stack[2] = stack[2] + 1 = 0 + 1 = 1

I2luY2x1ZGUgPGlvc3RyZWFtPgojZGVmaW5lIEZJTiAiZ3JhcGguaW4iCiNkZWZpbmUgU0laRSA1MAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYXRbU0laRV1bU0laRV0sIHN0YWNrW1NJWkVdLApub2RlcywKaywKc3RhcnRfbm9kZTsKCnZvaWQgbG9hZEdyYXBoKCkgewogICAgaW50IGksIGo7CiAgICAvL2ZyZW9wZW4oRklOLCAiciIsc3RkaW4pOwogICAgIC8vY2l0aW0gbnVtYXJ1bCBkZSBub2R1cmkKICAgICBjaW4+Pm5vZGVzOwoKICAgICAvL2NpdGltIG11Y2hpaWxlIChpLGopCiAgICAgLy9kZSBsYSBpIGxhIGogc2kgZGUgbGEgaiBsYSBpCiAgICAgd2hpbGUoY2luPj5pPj5qKSB7CiAgICAgICBtYXRbaV1bal0gPSAxOwogICAgICAgbWF0W2pdW2ldID0gMTsKICAgICB9Cn0KCnZvaWQgZGlzcGxheUdyYXBoKCkgewoKICAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG5vZGVzOyBpKyspIHsKICAgICAgICBmb3IoaW50IGogPSAxOyBqIDw9IG5vZGVzOyArK2opIHsKICAgICAgICAgIHByaW50ZigiJWQgIiwgbWF0W2ldW2pdKTsKICAgICAgICB9CgogICAgICAgIHByaW50ZigiXG4iKTsKICAgICB9Cn0KCnZvaWQgaW5pdCgpIHsKICAgIC8vayA9IDI7IHN0YWNrWzJdID0gMAogICAgc3RhY2tbIGsgXSA9IDA7Cn0KCmludCBzdWNjKCkgewoKICAgIGlmKHN0YWNrW2tdIDwgbm9kZXMpIHsvLzAgPCA5ID8KCiAgICAgICBzdGFja1trXSsrOy8vc3RhY2tba10gPSAxICsgMSA9IDIgKHZhcmZ1bCkgc3RhY2tba10gPSAyCiAgICAgICByZXR1cm4gMTsKICAgIH0KICAgIHJldHVybiAwOwp9CgppbnQgdmFsaWQoKSB7CgogICAgaWYoIW1hdFsgc3RhY2tbay0xXSBdIFsgc3RhY2tba10gXSkgcmV0dXJuIDA7CgogICAgZm9yKGludCBpID0gMTsgaSA8IGsgOyArK2kpCgogICAgICAgICAgIGlmKHN0YWNrW2ldID09IHN0YWNrW2tdKSByZXR1cm4gMDsKCiAgICByZXR1cm4gMTsKfQoKaW50IHNvbCgpIHsKCiAgICByZXR1cm4gKGsgPT0gbm9kZXMpICYmIChtYXRbIHN0YXJ0X25vZGUgXVsgc3RhY2tba10gXSA9PSAxKTsKfQoKdm9pZCBkaXNwbGF5X3NvbHV0aW9uKCkgewoKICAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG5vZGVzOyArK2kpIHByaW50ZigiJWQgIiwgc3RhY2tbaV0pOwoKICAgICBwcmludGYoIiVkIiwgc3RhcnRfbm9kZSk7CiAgICAgcHJpbnRmKCJcbiIpOwp9CgovL2JhY2t0cmFja2luZyBpdGVyYXRpdmUKdm9pZCBia3QoKSB7CgogICAgIGludCBoLCB2OwoKICAgICBrID0gMjsKCiAgICAgaW5pdCgpOwoKICAgICB3aGlsZShrID4gMSkgewoKICAgICAgICAgICBoID0gMTsKICAgICAgICAgICB2ID0gMDsKICAgICAgICAgICB3aGlsZShoICYmICF2KSB7CiAgICAgICAgICAgICAgIGggPSBzdWNjKCk7CiAgICAgICAgICAgICAgIGlmKGgpIHYgPSB2YWxpZCgpOwogICAgICAgICAgIH0KCiAgICAgICAgICAgaWYoaCkgewoKICAgICAgICAgICAgIGlmKHNvbCgpKSB7CiAgICAgICAgICAgICAgICBkaXNwbGF5X3NvbHV0aW9uKCk7CiAgICAgICAgICAgICAgICAvL2sgPSAxOwogICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgaysrO2luaXQoKTsKICAgICAgICAgICAgIH0KCiAgICAgICAgICAgfSBlbHNlIGstLTsKICAgICB9Cgp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhciBjb25zdCAqYXJndltdKSB7CgogIHByaW50ZigiJXMiLCJOb2R1bCBkZSBzdGFydCA9ICIpOwogIHNjYW5mKCIlZCIsICZzdGFydF9ub2RlKTsKCiAgbG9hZEdyYXBoKCk7CiAgcHJpbnRmKCIlc1xuIiwgIkdyYWZ1bCBuZW9yaWVudGF0Iik7CiAgZGlzcGxheUdyYXBoKCk7CgogIHN0YWNrWzFdID0gc3RhcnRfbm9kZTsKICAvL2sgPSAyOwogIC8vc3RhY2tbMl0gPSAxOwoKICBwcmludGYoIiVzXG4iLCJEcnVtdXJpIGhhbWlsdG9uaWVuZToiKTsKICBia3QoKTsKCiAgcmV0dXJuIDA7Cn0KCi8vaz0zOyBzdGFja1trXSA6MwovL2s9Mjsgc3RhY2tba10gOjIKICAgICAgICAgICAgICAgIC8vbXVjaGllCi8vaz0xOyBzdGFja1trXSA6MSAodmFyZikKCi8vc3RhY2tba10gPSBWYXJmCgovL25vZGVfc3RhcnQgPSA1CgovL3N0YWNrWzFdID0gNQoKICAgICAgICAgICAgIC8vaW5pdCgpCi8vc3RhY2tbMl0gPSBzdGFja1syXSArIDEgPSAwICsgMSA9IDEK

NQo5CjEgMgoxIDQKMiAzCjIgNAoyIDUKMyA0CjMgOAozIDkKNCA2CjUgNgo1IDcKNSA4CjcgOAo4IDkK

5
9
1 2
1 4
2 3
2 4
2 5
3 4
3 8
3 9
4 6
5 6
5 7
5 8
7 8
8 9