package lanqiao.递归;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main2 {
    private static final int N = 10; // 定义常量N，表示数组的最大大小为10
    private static int n; // 实际输入的整数n，表示要生成的排列长度
    private static int[] state = new int[N]; // 用于存储当前排列的数组
    private static boolean[] used = new boolean[N]; // 用于标记数字是否已被使用

    // 深度优先搜索函数，用于生成1到n的所有排列
    private static void dfs(int index) {
        // 当索引超过n时，表示一个完整排列生成
        if (index > n) {
            for (int i = 1; i <= n; i++) {
                System.out.print(state[i] + " "); // 输出当前排列
            }
            System.out.println(); // 换行，输出完一个排列
            return; // 结束当前递归
        }
        // 尝试将每个数字放在当前索引位置
        for (int i = 1; i <= n; i++) {
            if (!used[i]) { // 如果数字i未被使用
                state[index] = i; // 将i放入当前排列的位置
                used[i] = true; // 标记i为已使用
                dfs(index + 1); // 递归调用，处理下一个位置
                state[index] = 0; // 恢复现场，重置当前状态
                used[i] = false; // 恢复现场，标记i为未使用
            }
        }
    }

    // 主函数
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 创建BufferedReader读取输入
        StringTokenizer st = new StringTokenizer(br.readLine()); // 使用StringTokenizer分割输入

        n = Integer.parseInt(st.nextToken()); // 读取输入的整数n
        dfs(1); // 从索引1开始生成排列
    }
}