#include <iostream>
#include <fstream>
#include <vector>

static int numberOfPermutations;
static int solutionsCounter;
std::ofstream out("permutari.out");

void generatePermutations(std::vector<bool> &usedElements,
                          std::vector<int> &solution, int level)
{
    // daca dimensiunea este potrivita => afiseaza permutarea
    if (level == numberOfPermutations) {
        for (int i = 0; i < solution.size(); i++) {
            out << solution[i] << ' ';
        }
        out << "\n";
        solutionsCounter++;
        return;
    }

    // altfel -> genereaza permutare
    for (unsigned int i = 0; i < usedElements.size(); ++i) {
        // daca elementul nu a fost folosit
        if (!usedElements[i]) 
        {
            // marcheaza l ca folosit
            usedElements[i] = true;

            // creste dimensiunea solutiei
            solution[level] = i + 1;

            /* apeleaza functia de generare a permutarii
            pe sirul crescut cu un nivel (o cifra) */
            generatePermutations(usedElements, solution, ++level);
            
            /* marcheaza elementul ca nefolosit
            pt a genera o alta permutare => backtracking */
            usedElements[i] = false;

            // scade nivelul
            level--;
        }
    }
}

int main()
{
    std::ifstream fin("permutari.in");

    fin >> numberOfPermutations;
    solutionsCounter = 0;
    // true if i+1 was selected in the current partial solution, false otherwise
    std::vector<bool> usedElements(numberOfPermutations, false);
    // stores the solution
    std::vector<int> solution(numberOfPermutations, 0);

    generatePermutations(usedElements, solution, 0);
    std::cout << "Number of solutions: " << solutionsCounter << "\n\n";
    
    fin.close(); out.close();
    return 0;
}