在算法理论中，对必须输出的元素进行的计数叫做"平凡下界"，对于全排列问题不可能有复杂度小于O(n!)的算法，因为光输出语句的数量就是 n!了。
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入
一个整数 n 。(1 \leq n \leq 9 )
输出
输出由 1 至 n 组成的所有不重复数字序列，每行一个序列。每个数字之间用一个空格隔开。
样例
| 标准输入 复制文本 |
3 |
| 标准输出 复制文本 |
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 |