题目描述

写一个递归函数，枚举1∼n的所有排列方式（全排列枚举）. 若两种排列方法中前k−1个数相同，则第k个数更小的在前. 例如对n=3,应该按如下顺序给出结果

{1,2,3}{1,3,2},{2,1,3}{2,3,1},{3,1,2}{3,2,1}.

输入格式

一个正整数n

输出格式

n!行, 每行一个排列, 按题目要求顺序.

输入样例 #1

3

输出样例 #1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

输入样例 #2

1

输出样例 #2

1

输入样例 #3

2

输出样例 #3

1 2
2 1

数据范围与约定

1≤n≤8。