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

void back(int k, int n, vector<int> &vect, vector<vector<int> > &matr, vector<int> &valid) {
	for (int i = 1; i <= n; i ++) {
		vect[k] = i;
		cout << (i - 1) << " : " << valid[i - 1] << endl;
		if (valid[i - 1] == 0) {
			valid[i - 1] = 1;
			if (k == n - 1)
				matr.push_back(vect);
			else back(k + 1, n, vect, matr, valid);
			valid[i - 1] = 0;
		}
	}
}

int main() {
	ifstream infile; 
   	infile.open("permutari.in");
	ofstream outfile;
	outfile.open("permutari.out");

	int n;
	infile >> n;
	vector<int> vect(n), valid(n, 0);	
	vector<vector<int> > matr;	 
	back(0, n, vect, matr, valid);
	for (int i = 0; i < matr.size(); i ++) {
		for (int j = 0; j < matr[i].size(); j ++)
			outfile << matr[i][j] << " ";
		outfile << endl;
	}
	return 0;
}