题目：输出 1~n 的全排列

题目描述

从键盘读入一个整数 n（n ≤ 6），请输出 1 到 n 的所有全排列，并按字典序从小到大排列输出。

全排列的含义： 从 n 个互不相同的元素中取出 n 个并按某种顺序排列，称为这 n 个元素的一个全排列。

例如，当 n = 3 时，全排列为：

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

输入格式

输入一个整数：

n

其中 $(1 \le n \le 6)$。

输出格式

输出 1~n 的所有全排列，按字典序从小到大排列，每行输出一个排列，数字之间用空格隔开。

样例输入

3

样例输出

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