#include <iostream>
using namespace std;
#include <fstream>
#include <exception>

namespace e_011_perms
{
	void back_track_permutari(int k, int N, int* v, char* used, ofstream& ofs)
	{
		//if the sequence is full
		if (k == N+1) {
			//print the solution in file
			for (int i = 1; i <= N; i++) ofs << v[i] << " ";
			ofs << "\n";
		}
		else {
			//fill the element k with all posible values
			for (int i = 1; i <= N; i++) {
				if (!used[i]) {
					v[k] = i;
					used[i] = 1; //is used
					//fill the rest of the values
					back_track_permutari(k + 1, N, v, used, ofs);
					used[i] = 0; //the value i is no longer used in permutation
				}
			}
		}
	}
}

//int e_011_permutari()
int main()
{
	using namespace e_011_perms;
	int N;
	
	string fin = "permutari.in";
	ifstream ifs(fin);
	if (!ifs.is_open()) throw std::exception("Input file not found");
	ifs >> N;
	ifs.close();
	
	int* v = new int[N + 1];
	char* used = new char[N + 1];
	for (int i = 1; i <= N; i++) used[i] = 0; //initialization

	ofstream ofs("permutari.out");
	back_track_permutari(1, N, v, used, ofs);
	ofs.close();

	delete[] v;
	delete[] used;

	return 0;
}