/**
  Permutarile multzimii {1,2,...,n}

Ex: n=4
1 2 3 4       2 1 3 4       3 1 2 4       4 1 2 3
1 2 4 3       2 1 4 3       3 1 4 2       4 1 3 2
1 3 2 4       2 3 1 4       3 2 1 4       4 2 1 3
1 3 4 2       2 3 4 1       3 2 4 1       4 2 3 1
1 4 2 3       2 4 1 3       3 4 1 2       4 3 1 2
1 4 3 2       2 4 3 1       3 4 2 1       4 3 2 1
(sunt in nr. de 24)

  La aceasta solutzie am optimizat validarea termenilor: cu ajutorul unui vector
de marcare evitam for-ul din validul solutziei anterioare

  Solutzia de mai jos este deja backtracking.

  Optimizarea adusa consta in verificarea fiecarui x[k] IMEDIAT ce a fost generat,
daca e capabil sa conduca la o solutzie.
  In cazul nostru, al permutarilor, trebuie sa verificam faptul ca el NU se repeta
printre valorile aflate inaintea sa.
   In teoria pb. de back aceasta operatzie se numeshte "validare".
*/
#include <cstdio>
#include <cstring>
using namespace std;

int x[30],n,used[30];

FILE *f=fopen("permutari.out","w");

void afish()
{
    //testam dak sunt distincte:
    int i;
    for(int i=1;i<=n;i++)
        fprintf(f,"%d ",x[i]);
    fprintf(f,"\n");
}

void gen_prod_cart(int k)
{
    for(x[k]=1;x[k]<=n;x[k]++)
        if(!used[x[k]])//daca valoarea pusa de catre for in x[k] NU e deja utilizata, e ok
        {
            used[x[k]]=1;
            if(k==n)
                afish();
            else
                gen_prod_cart(k+1);
            ///la intoarcere o eliberam:
            used[x[k]]=0;
        }
}

int main()
{
    FILE *f1=fopen("permutari.in","r");
    fscanf(f1,"%d",&n);
    gen_prod_cart(1);
    return 0;
}