#include <stdio.h>
#include <stdlib.h>

// Pseudocode:
// nest position = 0 to n-1
//      for list[position] = 0 to n-1
//              if list[position] != position and list[position] not in list
//                      deeper;
//              end
//      do
//              for element in list
//                      print element+1;
//      end

// returns 1 if element is not in list up to size
// returns 0 otherwise
int not_in_list(int element, int *list, int size) {
        int list_iterator;
        for(list_iterator = 0; list_iterator < size; list_iterator++) {
           if(list[list_iterator] == element) {
                   return 0;
           }
        }          
        return 1;
}

// prints each element incremented by one in list of size
void print_list(int *list, int size) {
        int list_iterator;
        for(list_iterator = 0; list_iterator < size; list_iterator++) {
                printf("%d\t",(list[list_iterator])+1);
        }
        printf("\n");
}

int main(int argc, char *argv[]) {
        int position, arg_iterator, n;
        int *list;

        // iterate through each argument
        // and print the derangement for each one
        for(arg_iterator = 1; arg_iterator < argc; arg_iterator++) {
                n = atoi(argv[arg_iterator]); 
                printf("%d:\n",n);

                position = 0;
                list = malloc(sizeof(int)*(n));
                goto cmpfinal;

        increment:
                position = position + 1;
        cmpfinal:
                if (position > (n-1)) {
                        goto body;
                } else {
                        list[position] = -1;
        replicated:
                        while(list[position] < (n-1)) {
                                list[position]++;
                                // element is not in the "right" place
                                // and is not already in the list up to this position
                                if((list[position] != position) 
                                        && not_in_list(list[position],list,position)) {
                                        goto increment; // deeper;
                                }
                        }
                }
                goto decrement;

        body:
                print_list(list,n);

        decrement:
                position = position - 1;
        // cmpinit:
                if (position < 0) {
                        goto end;
                } else {
                        goto replicated;
                }
        end:
                free(list);
        }

        return 0;
}