Untitled

#include <bits/stdc++.h>

using namespace std;

int n, v[10], k;

void afisare(int k, int v[]){
    for(int i=1; i<=k; i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

bool isok(int k, int v[]){
    for(int i=1; i<=k-1; i++){
        if(v[i]==v[k]){ 
            return false;
        }
        if(k%2==0 && v[k]!=k){
            return false;
        }
    }
    return true;
}

void backtracking(int n, int v[], int k){
    for(int i=1; i<=n; i++){
        v[k]=i;
        if(isok(k, v)){
            if(k==n){
                afisare(k, v);
            }
            else{
                backtracking(n, v, k+1);
            }
        }
    }
}

void solve(){
    cin>>n;
    backtracking(n, v, 1);
}

int main(){
   solve();
    return 0;
}